题目描述
给出一个整数 n 和 k 个变换规则。
规则：
- 一位数可变换成另一个一位数。
- 规则的右部不能为零。
例如：n=234,k=2。有以下两个规则：
- 2⟶5。
- 3⟶6。
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
- 234。
- 534。
- 264。
- 564。
共 4 种不同的产生数。
现在给出一个整数 n 和 k 个规则。求出经过任意次的变换（0 次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入格式
第一行两个整数 n,k，含义如题面所示。
接下来 k 行，每行两个整数 x**i,y**i，表示每条规则。
输出格式
共一行，输出能生成的数字个数。
输入输出样例
输入 #1复制
234 2
2 5
3 6
输出 #1复制
4
说明/提示
对于 100% 数据，满足 $n<10^30$，k≤15。
算法分析
对于n的每一位，都可以用DFS跑一边，看看有多少种形态，最后把每一位算出来的形态种数相乘就可以了。但注意到n最多有30位，每位最多有9种形态，答案最大有$9^30$，用long long会直接爆炸，怎么办呢？有两种做法，一种刁钻的做法是用__int128存答案，但输出时只能用快写输出。还有一种做法是用万能的高精度做，简（fu）单（za）好（shao）写（nao）。
于是我们就得出了一下两种代码：
刁钻做法：
#include<bits/stdc++.h>
using namespace std;
string n;
int k;
int cnt = 0;
vector<int> b[15];
__int128 sum = 1;
bool vis[1005];
void print(__int128 t){//快些if(t<0){//此处可有可无putchar('-');t = 0-t;}if(t>9){print(t/10);}putchar(char(t%10+'0'));
}
void dfs(int x){//DFS遍历形态种数vis[x] = 1;cnt++;for(auto i : b[x]){if(vis[i]==0){dfs(i);}}
}
int main(){cin>>n>>k;for(int i = 1; i<=k; i++){int x,y;cin>>x>>y;b[x].push_back(y);}int len = n.size();for(int i = 0; i<len; i++){cnt = 0;memset(vis,0,sizeof(vis));int t = n[i]-'0';dfs(t);sum*=cnt;}print(sum);//输出方案数return 0;
}
高精度做法：
#include<bits/stdc++.h>
using namespace std;
string n;
int k;
int cnt = 0;
int len = 1;//高精度数的长度
vector<int> b[1005];
int a[1005];//高精度数组
bool vis[1005];
void print(){for(int i = len; i>=1; i--){cout<<a[i];}
}
void cheng(int t){//高精度函数int tlen = len;for(int i = 1; i<=len; i++){a[i]*=t;//每位都先乘一遍}for(int i = 1; i<=tlen; i++){if(a[i]>9){if(i==len){//位数不够，长度+1len++;}a[i+1]+=a[i]/10;//进位a[i]%=10;}}
}
void dfs(int x){//DFS遍历形态种数vis[x] = 1;cnt++;for(auto i : b[x]){if(vis[i]==0){dfs(i);}}
}
int main(){cin>>n>>k;for(int i = 1; i<=k; i++){int x,y;cin>>x>>y;b[x].push_back(y);}a[1] = 1;//初始化int tlen = n.size();for(int i = 0; i<tlen; i++){cnt = 0;memset(vis,0,sizeof(vis));int t = n[i]-'0';dfs(t);cheng(cnt);//调用函数}print();//输出return 0;
}