P1037 [NOIP2002 普及组] 产生数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lint long long
#define pb push_back
lint k,x[20],y[20],len,ans[10010],jw[10010];
int m[20]={0};
string s;
void dfs(int d){
if(m[d]) return ; //记忆化搜索
m[d]=1; //如果能变换为d，就标记为1
for(int i=1;i<=k;i++) if(x[i]==d) dfs(y[i]);
}
int main(){
cin >> s >> k;
for(int i=1;i<=k;i++) cin >> x[i] >> y[i];
memset(ans,-1,sizeof(ans));
ans[1]=1;
len=s.size();
for(int i=0;i<len;i++){ //能产生的数的总数等于每位能变换的数的个数
int d=s[i]-'0',add=0;
memset(m,0,sizeof(m));
dfs(d);
for(int i=0;i<=9;i++) if(m[i]) add++; //统计第i位能变换的数的个数
memset(jw,0,sizeof(jw));
int j=1;
while(ans[j]>=0){ //高精乘低精
jw[j+1]=(ans[j]*add)/10; //jw数组储存进位的数
ans[j]=(ans[j]*add)%10;
j++;
}
for(int k=1;k<=j;k++){
if(ans[k]==-1 ) ans[k]=jw[k];
else ans[k]+=jw[k];
if(ans[k]>=10){ans[k+1]+=ans[k]/10; ans[k]%=10;}
}
}
int i=10000;
while(ans[i]<=0) i--; //去前导零
for(int j=i;j>=1;j--) cout << ans[j];
return 0;
}
