【题目来源】
洛谷：[P1037 NOIP 2002 普及组] 产生数 - 洛谷 (luogu.com.cn)
【题目描述】
给出一个整数 \(n\) 和 \(k\) 个变换规则。
关于规则：
- 一位数可变换成另一个一位数：
- 规则的右部不能为零。
例如：\(n=234\)，有 \(k=2\) 个规则：
- \(2\rarr 5\)
- \(3\rarr 6\)
上面的整数 \(234\) 经过变换后可能产生出的整数为（包括原数）:
- \(234\)
- \(534\)
- \(264\)
- \(564\)
共 \(4\) 种不同的产生数。
给出一个整数 \(n\) 和 \(k\) 个规则，请你计算，经过任意次的变换（\(0\) 次或多次），能产生出多少个不同整数。
仅要求输出个数。
【输入】
第一行包含两个整数 \(n,k\)。
接下来 \(k\) 行，每行包含两个整数 \(x_i,y_i\)，表示一条规则为 \(x_i\rarr y_i\)。
【输出】
一个整数，表示能生出的不同整数的个数。
【输入样例】
234 2
2 5
3 6
【输出样例】
4
【算法标签】
《洛谷 P1037 产生数》 #高精度# #深度优先搜索DFS# #NOIP普及组# #2002#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;const int N = 35; // 定义常量：N为节点数量上限
int dist[11][11]; // dist[i][j]：数字i是否可以转换为数字j（1表示可以，0表示不可以）
int num[11]; // num[i]：数字i可以转换的数字种类数
string str; // 存储输入的整数字符串
int k; // 规则数量
int t[N]; // t[i]：整数第i位数字的变换种类数
vector<int> ans; // 存储最终结果的每一位数字// Floyd-Warshall算法实现
void floyd()
{// 三重循环，k是中间节点，i是起点，j是终点for (int k = 1; k <= 9; k++)for (int i = 0; i <= 9; i++)for (int j = 0; j <= 9; j++)// 如果i可以转换为k，且k可以转换为j，则i可以转换为jif (dist[i][k] && dist[k][j])dist[i][j] = 1;
}// 高精度乘法：将高精度数A乘以整数b
vector<int> mul(vector<int> A, int b)
{int t = 0; // 进位vector<int> C; // 存储结果for (int i = 0; i < A.size() || t > 0; i++) {if (i < A.size()) t = A[i] * b + t; // 计算当前位的乘积并加上进位C.push_back(t % 10); // 将当前位的值加入结果t = t / 10; // 计算进位}return C; // 返回结果
}int main()
{cin >> str >> k; // 输入整数字符串和规则数量// 初始化dist数组for (int i = 1; i <= k; i++) {int a, b;cin >> a >> b; // 输入规则：a可以转换为bdist[a][b] = 1; // 标记a可以转换为b}floyd(); // 调用Floyd-Warshall算法，计算所有数字之间的转换关系// 计算每个数字可以转换的数字种类数for (int i = 0; i <= 9; i++) {dist[i][i] = 1; // 每个数字可以转换为自身for (int j = 0; j <= 9; j++)if (dist[i][j] == 1) num[i]++; // 统计数字i可以转换的数字种类数}int len = str.size(); // 获取整数的位数// 计算每一位数字的变换种类数for (int i = 0; i < len; i++) {t[i] = num[str[i] - '0']; // 将字符转换为数字，并获取其变换种类数}// 初始化结果为第一位数字的变换种类数ans.push_back(t[0]);// 依次乘以每一位数字的变换种类数for (int i = 1; i < len; i++) {vector<int> D = mul(ans, t[i]); // 高精度乘法ans = D; // 更新结果}// 输出结果（从高位到低位）for (int i = ans.size() - 1; i >= 0; i--) {cout << ans[i];}return 0; // 程序结束
}
【运行结果】
234 2
2 5
3 6
4