Luogu 产生数

题解

题意

给出 $k$ 个变换规则，形如 a->b 表示 $a$ 可以变为 $b$, 问一个数 $n$ 的任意位上经过任意次的变换后能形成最多多少个新数。

解

组合问题
将所有位上的变化的方案相乘就是最后答案
变化方案有直接的和间接地，通过 $floyd$ 可以求出。
然后高精相乘，必须用到高精。

Code

#include <iostream>
#include <string>
using namespace std;
string str;
int k, vis[10][10], f[10], num[101];
int main() {
    cin >> str >> k;
    while(k--) {
        int a, b;
        cin >> a >> b;
        vis[a][b] = true;
    }
    for(int i = 0; i <= 9; i ++) vis[i][i] = true;
    for(int k = 0; k <= 9; k ++)
        for(int i = 0; i <= 9; i ++)
            for(int j = 0; j <= 9; j ++) 
                vis[i][j] = vis[i][j] || (vis[i][k] && vis[k][j]);
    for(int i = 0; i <= 9; i ++)
        for(int j = 0; j <= 9; j ++)
            if(vis[i][j]) f[i] ++;
    int len = 2;
    num[1] = 1;
    for(int i = 0; i < (int)str.length(); i++) {
        for(int j = 1; j <= 100; j ++) num[j] *= f[str[i] - '0'];
        for(int j = 1; j <= 100; j ++)
            if(num[j] >= 10) {
                num[j + 1] += num[j] / 10;
                num[j] %= 10;
            }
        while (num[len]) len ++;
    }
    for (int i = len - 1; i >= 1; i --) cout << num[i];
    return 0;
}