背景

给出一个整数 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

样例输入1

234 22 53 6

样例输出1

4

限制

每个测试点1s

来源

noip2002普及组第三题

 

－－－－－－－－－－－－－－－－

一个数可以变换多次，floyd求传递闭包(初始化d[i][i]=1)，乘法原理更新答案

要用高精度，注意输出

////  main.cpp//  noip2002产生数////  Created by Candy on 9/10/16.//  Copyright © 2016 Candy. All rights reserved.//#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef unsigned long long ll;const int N=55,B=1e4;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int k,x,y,d[N][N],f[N];char s[N];void floyd(){    for(int i=0;i<=9;i++) d[i][i]=1;    for(int k=0;k<=9;k++)        for(int i=0;i<=9;i++)            for(int j=0;j<=9;j++)                d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);    for(int i=0;i<=9;i++)        for(int j=0;j<=9;j++) if(d[i][j]) f[i]++;}struct big{    int d[100],size;    big(){size=1;}} ans;void chengInt(big &a,int k){    int g=0,i;    for(i=1;i<=a.size;i++){        int tmp=a.d[i]*k;        a.d[i]=(tmp+g)%B;        g=(tmp+g)/B;    }    while(g){        a.d[i++]=g%B; a.size++;        g/=B;    }}int main(int argc, const char * argv[]) {    scanf("%s%d",s,&k);    for(int i=1;i<=k;i++) scanf("%d%d",&x,&y),d[x][y]=1;    floyd();    ans.d[1]=1;    int len=strlen(s);    for(int i=0;i
           
            =1;i--){        if(i!=ans.size){            if(ans.d[i]<10) cout<<"000";            else if(ans.d[i]<100) cout<<"00";            else if(ans.d[i]<1000) cout<<"0";        }        cout<