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;}