传递闭包+乘法原理+高精。
变换具有传递性,如\(2→3\),\(3→5\),则有变换\(2→5\)。
首先我们根据输入的变换规则构造一个图\(G\),其顶点为\(0 \sim 9\)这\(10\)个数字,边\((X,Y)\) 权值为1表示规则\(x→y\),否则为\(0\)。于是可以根据Floyd算法求出图\(G\)的传递闭包。那么答案就是输入整数的每一位能够在传递闭包中到达的(包含其自身)顶点数之和。
之后根据乘法原理,分别考虑每一位取值的个数,得到总的方案数。
const int N=35;
struct bignum
{
int m[N];
int len;
bignum()
{
memset(m,0,sizeof m);
len=0;
}
};
char s[N];
bool g[10][10];
int cnt[10];
int n,m;
void floyd()
{
for(int k=0;k<10;k++)
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
g[i][j] |= g[i][k] & g[k][j];
}
bignum mul(bignum a,int b)
{
bignum c;
c.len=a.len;
int carry=0;
for(int i=0;i<c.len;i++)
{
int t=a.m[i]*b+carry;
c.m[i]=t%10;
carry=t/10;
}
while(carry)
{
c.m[c.len++]=carry%10;
carry/=10;
}
return c;
}
int main()
{
scanf("%s%d",s,&m);
n=strlen(s);
for(int i=0;i<10;i++) g[i][i]=true;
while(m--)
{
int a,b;
cin>>a>>b;
g[a][b]=true;
}
floyd();
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
if(g[i][j])
cnt[i]++;
bignum res;
res.m[0]=1;
res.len=1;
for(int i=0;i<n;i++)
res=mul(res,cnt[s[i]-'0']);
for(int i=res.len-1;i>=0;i--)
cout<<res.m[i];
cout<<endl;
//system("pause");
return 0;
}