题解 P1037 【产生数】
yang2016
·
·
题解
#include<iostream>
#include<cstring>
#include<string>
bool f[10][10];
int k,ans[500]={1},l=1;
using namespace std;
void wk(int x)//高精度乘法
{
for(int i=0;i<l;i++)
ans[i]*=x;
for(int i=0;i<l;i++)
if(ans[i]>=10){ans[i+1]+=ans[i]/10;ans[i]%=10;}
while(ans[l]>0){
ans[l+1]=ans[l]/10;
ans[l]=ans[l]%10;
l++;
}
}
int main(){
string a;
cin>>a>>k;
int x,y;
for(int i=1;i<=k;i++) { cin>>x>>y;f[x][y]=1; }
for(int i=0;i<=9;i++) f[i][i]=1; //数字是可以转化为自己的
for(int k=1;k<=9;k++) //用 floyd 计算每个数可以转换的数字(包括本身)
for(int i=0;i<=9;i++)
for(int j=1;j<=9;j++)
if(f[i][k]&&f[k][j])f[i][j]=1;
int b[10];
for(int i=0;i<=9;i++){ //统计每个数可以转换的数字数
int tot=0;
for(int j=0;j<=9;j++)
if(f[i][j]) tot++;
b[i]=tot;
}
for(int i=0;i<a.length();i++) wk(b[a[i]-'0']); //乘法原理
for(int i=l-1;i>=0;i--) cout<<ans[i];
return 0;
}