problem
- 给定一个整数n和k个变换规则(一位数可变换成另一个一位数)
- 经过任意次的变换( 0 次或多次),能产生出多少个不同整数
- n < 1e30, k <= 15
例:
n=234 。有规则( k=2 ):22 -> 55 且 33 -> 66
则能产生234、534、264、564四种数
solution
- 一共有15种操作,说明一个数能变成多个不同的数。比如a->b,且b->c,那么存在a->c。可以DFS搜索出每个数能到达的其他所有数的个数(1~9)
- 最多可能有30位数,所以复杂度上限O(9^30)。乘法要用高精且每次乘数不超过9。
codes
#include<iostream> #include<string> #include<cstring> using namespace std; //search const int maxk = 20; int op[maxk][maxk], ss, vis[maxk]; void dfs(int x){ if(vis[x])return ; vis[x] = 1; ss++; for(int i = 0; i <= 9; i++) if(op[x][i])dfs(i); } //高精度 *= 低精(只有1位) int val[33], len = 1; void mul(int x){ int t = 0; //进位 for(int i = 1; i <= len; i++){ val[i] = val[i]*x+t; t = val[i]/10; val[i] %= 10; } if(t > 0)val[++len] = t; return ; } int main(){ //datein string s; int k; cin>>s>>k; if(k==0){cout<<1;return 0;} for(int i = 1; i <= k; i++){ int a, b; cin>>a>>b; op[a][b] = 1; } //每个数可以转化的个数 val[1] = 1; //高精初始化 for(int i = 0; i < s.size(); i++){ memset(vis,0,sizeof(vis)); ss=0;//初始化 dfs(s[i]-'0');//搜索并更新ss的值 mul(ss);//累加答案 } //dateout for(int i = len; i >= 1; i--) cout<<val[i]; cout<<'\n'; return 0; }