2350 - 产生数
给出一个整数n（n<1030) 和k个变换规则（k<=15）。
<span style="line-height:1.5;">规则：</span>
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2->5
<span style="line-height:1.5;"> 3->6</span>
<span style="line-height:1.5;"> 上面的整数234经过变换后可能产生出的整数为（包括原数）：</span>
<span style="line-height:1.5;"> 234</span>
<span style="line-height:1.5;"> 534</span>
<span style="line-height:1.5;"> 264</span>
<span style="line-height:1.5;"> 564</span>
<span style="line-height:1.5;"> 共4种不同的产生数</span>
问题：
<span style="line-height:1.5;">求出：</span>
经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。
<br />
题目输入
每个测试文件只包含一组测试数据，每组输入的第一行输入两个整数n和k（n<1030，k<=15）。
接下来k行每行输入一个规则，每个规则由两个整数构成。
题目输出
对于每组输入数据，输出一个整数，表示满足条件的个数。
输入/输出样例
题目输入
234 2 2 5 3 6
题目输出
4
C++解答
#include<stdio.h> #include<string.h> bool can[10][10]; int rules[10]; int ans[1000000]; int len,n,k; char s[100]; int main() { int i,j; scanf("%s",s); scanf("%d",&k); for ( i=1;i<=k;++i) { int a,b; scanf("%d%d",&a,&b); can[a][b]=true; } for ( i=0;i<10;++i) can[i][i]=true; for (int k=0;k<10;++k) for ( i=0;i<10;++i) for ( j=0;j<10;++j) can[i][j]=can[i][j]||(can[i][k]&&can[k][j]); for ( i=0;i<10;++i) for ( j=0;j<10;++j) if (can[i][j]) ++rules[i]; ans[1]=len=1; for ( i=0;i<strlen(s);++i) { int x=rules[s[i]-'0']; for ( j=1;j<=len;++j) ans[j]*=x; for ( j=1;j<=len;++j) { ans[j+1]+=ans[j]/10; ans[j]%=10; } while (ans[len]) { ans[len+1]+=ans[len]/10; ans[len]%=10; ++len; } } for ( i=len-1;i>0;--i) printf("%d",ans[i]); puts(""); return 0; }