2002NOIP普及组真题 3. 产生数
线上OJ 地址：
【02NOIP普及组】产生数
核心思想：组合数 + dfs + 高精度
1、如果一个数字有 3 位，每位有 2种可能性，则数字的 组合数 为 2*2*2 = 8 种 。故，只要求出每一位数字有多少种变体即可。
求 0 ~ 9 每一个数字的变体数量，可使用dfs深搜，并将结果存储在对应的 c[i] 中
具体方法：对 0 ~ 9 每一个数字执行一次 dfs，统计该数字发生的变体数量（最终要加上自己，比如 2 →3，3 →5，则最终该位置有 3 种数字的变体（分别为3，5和自身2））
2、把输入的字符串转换成 int 数组
3、最终结果 = 每一位变体数量的乘积 。如 2*2*2 = 8 种
由于 n 能达到 1 0 30 10^{30} 1030，所以 n 的位数可达31位，每一位都有 [1 ~ 10] 种变体，所以 10*10*10… *10 就变成了高精度乘法（高精度✖️低精度）。
4、最后注意结果为逆序输出
void Multiply(int a[], int b) // 高精乘低精 a[] * b 赋值给 a[]。
{int t = 0, i; // c存储进位 for(i = 1; i <= a[0]; ++i) // 注意：a数组存储的是逆序{a[i] = a[i] * b + t;t = a[i] / 10;a[i] %= 10; }while(t > 0) // 处理最后一次相乘产生的进位{a[i] = t % 10;t /= 10;i++;}while(a[i] == 0 && i > 1) // 消除 a[] 的前导0 i--;a[0] = i; // a[0]存储 a数组长度
}
题解代码：
#include<bits/stdc++.h>
using namespace std;const int K = 20;
const int N = 35;int k, cnt = 0, c[10]; // 用于存储 0~9 这10个数每个数可以变的次数。举例：1可以变为3和 5，则 c[1]=3；2可以变为6、7、8、9，则c[2]=5
int vis[10]; // 用于记录每个数字是否被访问过
int x[K], y[K]; // 记录每次读进来的规则，举例：第一个规则是 2 →3，则 x[1]=2; y[1]=[3]; 第二个规则是 3 →5，则 x[2]=3; y[2]=[5]void dfs(int a)
{for(int i = 1; i <= k; ++i){if(x[i] == a && vis[y[i]] == false){vis[y[i]] = true;cnt++; dfs(y[i]);}}
}void init()
{for(int i = 0; i <= 9; ++i){memset(vis, 0, sizeof(vis));//vis[j]:i能否通过应用某些规则变成数字j cnt = 0; // cnt 用于记载当前数字可以转变为多少个数字。举例： 2 →3， 3 →5，则表示 2可以转变为 2个数字（3和5），故cnt为2 vis[i] = true;dfs(i);//标记vis // 在执行 dfs 时，cnt会不断增加 c[i] = cnt + 1; // 加上自身后，存储在该数字对应的数组下标中。举例： 2 →3， 3 →5，则最终该位置有 3 种数字的组合（分别为3，5和自身2） }
}void Multiply(int a[], int b) // 高精乘低精 a * b 赋值给 a。
{int t = 0, i; // c存储进位 for(i = 1; i <= a[0]; ++i){a[i] = a[i] * b + t;t = a[i] / 10;a[i] %= 10; }while(t > 0){a[i] = t % 10;t /= 10;i++;}while(a[i] == 0 && i > 1) // 消除前导0 i--;a[0] = i; // a[0]存储 a数组长度
}int main()
{string s; cin >> s >> k;for(int i = 1; i <= k; ++i) cin >> x[i] >> y[i];// 第一步：对 0~9 每一个数字执行一次 dfs，统计该数字发生的变体数量（最终要加上自己，比如 2 →3，3 →5，则最终该位置有 3 种数字的变体（分别为3，5和自身2）） init(); // 第二步：把输入的字符串转换成int数组 int a[N]; // 用于存储拆分的数字 a[0] = s.length(); // 输入数字的长度 for(int i = 1; i <= a[0]; i++) a[i] = s[i-1] - '0'; // 第三步：最终结果 = 每一位变体数量的乘积 。如 2*2*2 = 8 种 int f[N]; // f[i]：前i位数字可以变换成的数字种类memset(f, 0, sizeof(f));f[0] = f[1] = 1;for(int i = 1; i <= a[0]; ++i) Multiply(f, c[a[i]]); // f * c[a[i]] 赋值回 f for(int i = f[0]; i >=1 ; i--) cout << f[i]; // 逆序输出 return 0;
}