題目描述
給出一個整數 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.新聞熱點
疑難解答
