知识点：搜索+高精度。

大体思路：

1.  我们求出每一位可以变换的数的个数。再用乘法原理一个一个乘起来。乘的时候用高精度。

2.  怎么求每一位可以变换成哪些数呢？搜索。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

char tmp1[1009];
int k,len1;
int s[1009];//数字串n 
int cnt[1009];//cnt[i]表示i可以变换的数的个数
int num[1009][1009];//num[i][1]表示i可以变成num[i][1] 
long long ans[1009];//ans[i]表示第i位的变换总数
int vis[1009]; 
int lastans[100009],digit=1;

void dfs(int nums,int ii){
	if(vis[nums] == 1)return;//注意这里要回溯！
	
	if(vis[nums] == 0){
		vis[nums] = 1;
		ans[ii]++;
	}
	
	for(int k=1; k<=cnt[nums]; k++){
		int nown = num[nums][k];
		dfs(nown,ii);
	}
}

void init(){
	for(int i=0; i<109; i++)vis[i] = 0;
}

void mul(int tt){
	int carry=0;//进位 
	for(int i=31; i>31-digit; i--){
		int ll = lastans[i]*tt+carry;
		carry = ll/10;
		lastans[i] = ll%10;
	}
	if(carry > 0){
		digit++;
		lastans[31-digit+1] = carry;
	}
}

int main(){
	cin >> tmp1 >> k;
	len1 = strlen(tmp1);
	for(int i=0; i<len1; i++) s[i+1] = tmp1[i]-'0';
	
	for(int i=1; i<=k; i++){
		int x,y;
		cin >> x >> y;//x可以变成y 
		cnt[x]++;
		num[x][cnt[x]] = y; 
	}
	
	lastans[31] = 1;
	
	for(int i=1; i<=len1; i++){
		init();//每一次都要清空 vis 数组
		dfs(s[i],i);
		mul(ans[i]);
	}
	
	int start=1;
	for(int i=1; ; i++){//删除前导0 
		if(lastans[i] == 0)start++;
		else break;
	}
	for(int i=start; i<=31; i++)cout << lastans[i];
	return 0;
} 

我一开始用 dp，拿到了 60pts，后来发现可以是经过多次“辗转”，变成另一个数，然后就放弃了，感觉 dp 不行。不过现在觉得 dp 好像是可行的，只不过也需要用 dfs 求出来一个数可以变成多少个数。 

转移方程应该就是 $f_i=f_{i-1} \times cnt$ （$cnt$ 就是第 $i$ 个位置上的数可以变成多少个数，那个个数） 注意 $f_0=1$