1004: 产生数

Description

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

Input

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

Output

　 屏幕输出，格式为：一个整数（满足条件的个数）：

Sample Input

234 22 53 6
Sample Output
4
HINT
Source
NOIP2002
[Submit][Status]
#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(){    scanf("%s",s);    scanf("%d",&k);    for (int i=1;i<=k;++i)    {        int a,b;        scanf("%d%d",&a,&b);        can[a][b]=true;    }    for (int i=0;i<10;++i) can[i][i]=true;    for (int k=0;k<10;++k)        for (int i=0;i<10;++i)            for (int j=0;j<10;++j)                can[i][j]=can[i][j]||(can[i][k]&&can[k][j]);    for (int i=0;i<10;++i)        for (int j=0;j<10;++j)            if (can[i][j]) ++rules[i];    ans[1]=len=1;    for (int i=0;i<strlen(s);++i)    {        int x=rules[s[i]-'0'];        for (int j=1;j<=len;++j) ans[j]*=x;        for (int 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 (int i=len-1;i>0;--i) PRintf("%d",ans[i]);    return 0;}