# Prob.3 of NOIP 2002 (Junior) *Solution*

More than two years ago, I thought it was an Ad Hoc problem and I had a try, but I failed.

Now I've realized it is just a math problem with floyd!

"Sky Gate":http://www.luogu.org/problem/show?pid=1037

Given a positive integer number n, and k ways of changing a digit. You could change a digit in a way called x y. Which means you could change number x into y. Then how many numbers could be produced after a series of changing operations? (Caution: We could change 0 times) Input: n k xi yi(1<=i<=k) Output: The answer required Sample Input: 234 2 2 5 3 6 Sample Output: 4 Explanations: 234, 264, 534, 564 are numbers available. For all 5 testcases: 1<=n<=10^30, 1<=k<=15, 0<=xi<=9, 1<=yi<=9

It's a problem of calculating the number of possible answers, but not a problem requiring every answer. So it's not recommended to use BFS, and that's why I failed two years ago...

Consider this situation: If a[i] means the number of ways that the i-th digit could change into, then the answer to the question is Πa[i]. It's obvious since every number couldn't be changed into zero unless it is zero at the beginning.

So use floyd to get can[i][j] indicating whether i could be changed into j.

Then get a[i]=Σcan[i][j].

Now calculate Πa[i] with higher precision.

Then it comes to coding...

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <ctime> #include <cmath> #include <algorithm> using namespace std; int k,i,j,jw,x,y,ans[110],st[110],len,f[110]; bool a[10][10]; char c; int main() { while((c=getchar())!=' ')st[++len]=c-48; scanf("%d",&k); for(i=1;i<=k;i++){scanf("%d%d",&x,&y);a[x][y]=1;}for(i=0;i<=9;i++)a[i][i]=1; for(i=1;i<=9;i++)for(j=0;j<=9;j++)for(k=1;k<=9;k++)a[j][k]=a[j][k]||a[j][i]&&a[i][k]; ans[0]=ans[1]=1; for(i=0;i<=9;i++)for(j=0;j<=9;j++)f[i]+=a[i][j]; for(i=1;i<=len;i++) { for(j=1;j<=ans[0];j++){ans[j]=ans[j]*f[st[i]]+jw;jw=ans[j]/10;ans[j]%=10;} while(jw){ans[++ans[0]]=jw%10;jw/=10;} } for(i=ans[0];i>=1;i--)printf("%d",ans[i]);puts("");return 0; }

Not very complex, in fact.

If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)