P1037 [NOIP2002 普及组] 产生数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
int d[20][20];
int f[25];
int num[150];
int main() {
	cin >> s;
	int n = s.length();
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		d[x][y] = 1;//有一条x->y的边
	}
	for (int i = 0; i <= 9; i++) d[i][i] = 1;//自己到自己也算

	for (int k = 0; k <= 9; k++)
		for (int i = 0; i <= 9; i++)
			for (int j = 0; j <= 9; j++)
				d[i][j] = (d[i][j] || (d[i][k] && d[k][j]));//i能变化成j，则标记可行
	for (int i = 0; i <= 9; i++)
		for (int j = 0; j <= 9; j++)
			if (d[i][j]) f[i]++;//查询每个数字可以变化的数量
	num[1] = 1;//初始为1
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < 100; j++) num[j] *= f[s[i] - '0'];//乘法
		for (int j = 1; j < 100; j++) {//高精度
			num[j + 1] += num[j] / 10;
			num[j] %= 10;
		}
	}
	int len = 110;
	while (len > 1 && !num[len]) len--;//去除前导0
	for (int i = len; i>=1; i--) cout << num[i];//逆序输出
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
int f[25],g[25],vis[25],q;
int num[150];
int ans;
void dfs(int n) {
	for (int i = 1; i <= q; i++) {
		if (f[i] == n && !vis[g[i]]) {//找到x->y，且y没有被访问过
			ans++;//变化+1
			vis[g[i]] = 1;//标记
			dfs(g[i]);//再从y开始寻找，是否有y->z的变化
		}
	}
}
int main() {
	cin >> s;
	int n = s.length();
	cin >> q;
	for(int i=1;i<=q;i++){
		int x, y;
		cin >> x >> y;
		f[i] = x, g[i] = y;//开两位数组，因为x可能会变化多个数字
	}
	num[1] = 1;
	for (int i = 0; i < n; i++) {
		memset(vis, 0, sizeof vis);//每次记得清空
		ans = 1;//开始时也要算上，顺便还原
		vis[s[i] - '0'] = 1;//标记已经变化过的点，防止产生环
		dfs(s[i] - '0');//深搜找能变化的个数
		for (int j = 1; j < 100; j++) num[j] *= ans;//乘法
		for (int j = 1; j < 100; j++) {
			num[j + 1] += num[j] / 10;
			num[j] %= 10;
		}
	}
	int len = 110;
	while (len > 1 && !num[len]) len--;
	for (int i = len; i>=1; i--) cout << num[i];
	return 0;
}