题目描述
给出一个整数 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
输出格式： 屏幕输出，格式为：
一个整数（满足条件的个数）：
输入输出样例
输入样例#1： 234 2 2 5 3 6 输出样例#1： 4
分析： 先用floyd求出每个数字能变成的其他数字求出，再用乘法原理求解，要用高精度。
代码：
var v,u,x,y:array[0..9]of longint; a:array[0..9,0..9]of longint; b:array[1..1000]of longint; sum:array[1..10000]of longint; i,t1,k,t,result,j,h:longint; c:char; w:array[0..9,0..9]of boolean;PRocedure cz;var i,j,k1:longint;begin for i:=0 to 9 do w[i,i]:=true; for k1:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do begin if (k1=i)or(i=j)or(i=k1)then h:=1 else if (w[i,j]=false)and(w[i,k1]=true)and(w[k1,j]=true)and(a[i,j]<a[i,k1]+a[k1,j])then begin w[i,j]:=true; a[i,j]:=a[i,k1]+a[k1,j]; end; end; for i:=0 to 9 do for j:=0 to 9 do if w[i,j] then inc(v[i]);end;procedure fj;var c:array[1..1000]of longint; x:longint;begin fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); x:=v[i]; t:=0; while x<>0 do begin inc(t); c[t]:=x mod 10; x:=x div 10; end; for j:=1 to t do b[j]:=c[j];end;procedure gj;var j,k:longint; su:array[1..10000]of longint;begin fillchar(su,sizeof(su),0); for j:=1 to t1 do su[j]:=sum[j]; fillchar(sum,sizeof(sum),0); for j:=1 to t1 do for k:=1 to t do begin sum[j+k-1]:=su[j]*b[k]+sum[j+k-1]; if sum[j+k-1]>9 then begin sum[j+k]:=sum[j+k-1]div 10; sum[j+k-1]:=sum[j+k-1]mod 10; if t1<j+k then t1:=j+k; end; if t1<j+k-1 then t1:=j+k-1; end;end;begin read(c); fillchar(w,sizeof(w),false); while c<>' 'do begin val(c,i,result); inc(u[i]); read(c); end; read(k); readln; for i:=1 to k do begin readln(x[i],y[i]); a[x[i],y[i]]:=1; w[x[i],y[i]]:=true; end; cz; sum[1]:=1; t1:=1; h:=0; for i:=0 to 9 do begin if (u[i]<>0)and(v[i]<>0) then begin fj; for j:=1 to u[i] do gj; end; end; for i:=t1 downto 1 do write(sum[i]);end.新闻热点
疑难解答
