NOIp2002普及组第三题 产生数

给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。 　　规则： 　　　一位数可变换成另一个一位数： 　　　规则的右部不能为零。 　　例如：n=234。有规则（k＝2）： 　　　　2－> 5 　　　　3－> 6 　　上面的整数 234 经过变换后可能产生出的整数为（包括原数）: 　　　234 　　　534 　　　264 　　　564 　　共 4 种不同的产生数 问题： 　　给出一个整数 n 和 k 个规则。 求出： 　　经过任意次的变换（0次或多次），能产生出多少个不同整数。 　　仅要求输出个数。 我自己算了一组数据： 比如输入： 1234 3 2 3 3 2 3 5 我自己算了只有6组 分别是： 1234 1224 1254 1334 1324 1354 可答案是要9组 各位高手们指点一下 还有3组是什么！ 随便告诉一下变化的放法！！！谢谢！

var a,ans:array[1..30] of longint;
f:array[0..9] of longint;
g:array[0..9,0..9] of boolean;
m,n,i,j,t,k:longint;
s:string;
begin
fillchar(g,sizeof(g),false);
fillchar(f,sizeof(f),0);
fillchar(ans,sizeof(ans),0);
readln(s);
n:=0; m:=0; i:=1;
while s[i] in ['0'..'9'] do
begin
inc(n); a[n]:=ord(s[i])-48; inc(i);
end;
while i<=length(s) do
begin
if s[i] in ['0'..'9'] then m:=m*10+ord(s[i])-48;
inc(i);
end;
for i:=1 to m do
begin
readln(t,j); g[t,j]:=true;
end;
for k:=0 to 9 do
for i:=0 to 9 do
for j:=0 to 9 do
g[i,j]:=g[i,j] or (g[i,k] and g[k,j]);
for i:=0 to 9 do g[i,i]:=true;
for i:=0 to 9 do
for j:=0 to 9 do
inc(f[i],ord(g[i,j]));
ans[1]:=1;
for k:=1 to n do
begin
j:=0;
for i:=1 to 30 do
begin
ans[i]:=ans[i]*f[a[k]]+j;
j:=ans[i] div 10;
ans[i]:=ans[i] mod 10;
end;
end;
j:=30;
while ans[j]= 0 do dec(j);
for i:=j downto 1 do write(ans[i]);
writeln;
end.

自己的，绝对正确！！！

你吖的 是高级计算机啊……

最后统计个数是要用到高精。

program c3;

const   MaxLen = 30;

var   Len, M: Byte;   a: array[1 .. MaxLen] of Byte;   f: array[0 .. 9] of Byte;   g: array[0 .. 9, 0 .. 9] of Boolean;

procedure Init; var   i: Byte;   St: String; begin   Readln(st);   Len := 0;  M := 0;   i := 1;   while st[i] in ['0' .. '9'] do     begin Inc(Len); a[Len] := Ord(st[i]) - 48; Inc(i) end;   Repeat     if st[i] in ['0' .. '9'] then M := M * 10 + Ord(st[i]) - 48;     Inc(i)   Until i > Length(st) end;

procedure Main; var   i, j, k: Byte; begin   Fillchar(g, Sizeof(g), False);   for k := 1 to M do     begin     Readln(i, j);     g[i, j] := True     end;   for k := 0 to 9 do     for i := 0 to 9 do     for j := 0 to 9 do     g[i, j] := g[i, j] or (g[i, k] and g[k, j]);   Fillchar(f, Sizeof(f), 0);   for i := 0 to 9 do g[i, i] := True;   for i := 0 to 9 do     for j := 0 to 9 do     Inc(f[i], Ord(g[i, j])) end;

procedure Show; var   i, j, k, g: Byte;   ans: Array[1 .. MaxLen] of Byte; begin   Fillchar(ans, Sizeof(ans), 0);   ans[1] := 1;   for k := 1 to Len do     begin     g := 0;     for i := 1 to MaxLen do     begin     ans[i] := ans[i] * f[a[k]] + g;     g := ans[i] div 10;     ans[i] := ans[i] mod 10     end     end;   j := MaxLen;   While ans[j] = 0 do Dec(j);   for i := j downto 1 do Write(ans[i]);   Writeln end;

begin   Init;   Main;   Show end.

经过任意次的变换（0次或多次）

那么 1234 ->1334

那么1334    3->5    1534

    1334  3->5   3->5    1554  

    1334->1324   3->5    1524

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息