问题 5119 --产生数-NOIP2002PJT3

5119: 产生数-NOIP2002PJT3

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 14
[提交][状态][讨论版][命题人:]

题目描述

产生数

(number.pas/c/cpp)

题目描述

  给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。
规则:
  一位数可变换成另一个一位数:
规则的右部不能为零。
  例如:n=234。有规则(k=2):
2-> 5
3-> 6
上面的整数 234 经过变换后可能产生出的整数为(包括原数):
234
534
264
564
共 4 种不同的产生数
问题:
给出一个整数 n 和 k 个规则。
求出:
经过任意次的变换(0次或多次),能产生出多少个不同整数。
仅要求输出个数。

输入格式

键盘输人,格式为:
   n k
   x1 y1
   x2 y2
   ... ...
   xn yn

输出

  屏幕输出,格式为:
一个整数(满足条件的个数):

样例输入

234 2
2 5
3 6

样例输出

4

提示


1.这题可以用搜索,搜索是可行的一种办法,dfs或bfs都可以,但是若平均每个数会有m种变换的话,那么复杂度将会是O(m^lgn),这无疑是非常巨大的.

2.其实可以观察到,题目并没有要求输出解,只要求输出解答个数,那么完全没必要用搜索.可以用数学的排列组合的方法过这题,设n1,n2,n3...nn分别有k1,k2,k3...kn种变换,那么加上那个数自己,每个数就有

k1+1,k2+1,k3+1...kn+1种取法,一共的取法也就是:



就是






用高精度运算就是了。Ki的求法可以用bfs,或者比较简便的floyd都可以求得。













参考代码,谢绝复制粘贴!



var

    map:array[0..9,0..9] of boolean;{构图,求一个数可以达到哪一个数}

    change:array[0..9] of integer;{每个数的取法总数,即上面说的ki}

    ans:array[0..10000] of integer;{累乘,计算上面的那个}

    k:integer;

    start:string;{需转换的数}

procedure init;

var

    i,x,y:integer;

    s:string;

begin

    fillchar(map,sizeof(map),false);

    readln(s);{读入s和规则总数k}

    i:=pos(' ',s);

    start:=copy(s,1,i-1);

    val(copy(s,i+1,length(s)),k,x);

    for i:=1 to k do{读入转换规则}

        begin

            readln(x,y);

            map[x,y]:=true;

        end;

    fillchar(change,sizeof(change),0);

    fillchar(ans,sizeof(ans),0);

    ans[0]:=1;

    ans[1]:=1;

end;

procedure floyd;

var

    i,j,kk:integer;

begin

    for kk:=0 to 9 do

        for i:=0 to 9 do

            for j:=0 to 9 do

                map[i,j]:=map[i,j] or(map[i,kk] and map[kk,j]);{求得一个数可以到达哪一个数}

    for i:=0 to 9 do

        map[i,i]:=true;{加上到它自己}

    for i:=0 to 9 do

        for j:=0 to 9 do

            if map[i,j] then inc(change[i]);{得到每个数可以扩展的取法数(ki)}

end;

procedure times(x:integer);{高精度累乘}

var

    i:integer;

begin

    for i:=1 to ans[0] do

        ans[i]:=ans[i]*x;

    for i:=1 to ans[0] do

        begin

            inc(ans[i+1],ans[i] div 10);

            ans[i]:=ans[i] mod 10;

        end;

    while ans[ans[0]]>0 do inc(ans[0]);

end;

procedure work;

var

    i,p:integer;

    t:boolean;

begin

    t:=false;

    for i:=1 to length(start) do

        t:=t or (change[ord(start[i])-48]>0);{专门针对无法转换情况优化}

    if not t then

        begin

            writeln(0);

            exit;

        end;

    for i:=1 to length(start) do

        times(change[ord(start[i])-48]);{计算}

    p:=ans[0];

    while ans[p]=0 do dec(p);

    for i:=p downto 1 do

        write(ans[i]);{输出答案}

    writeln;

end;

begin

    init;{初始化}

    floyd;{构图,算出Ki}

    work;{计算}

end.



来源

 

[提交][状态]