【正经题解】产生数

一个数字能变换的种类为可直接变换的和可间接变换的

比如 1 2 2 3

那么就自动多出来一个条件 1 3

就是1 有三种变化

这种情况用弗洛伊德算法 找到一个数字可以变化的次数和

之后在连续乘起来 得到的结果就是变化次数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stdlib.h>
using namespace std;

int tag[10][10];
int d[10];
int p[1000];

int main() {
    string a;
    int n;

    while (cin >> a >> n) {
        int x, y;

        // 读入关系并构建转化矩阵
        for (int i = 0; i < n; i++) {
            cin >> x >> y;
            tag[x][y] = 1;
        }

        // 使用 Warshall 算法构建关系闭包
        for (int k = 1; k <= 9; k++) {
            for (int i = 0; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    if (tag[i][k] && tag[k][j]) {
                        tag[i][j] = 1;
                    }
                }
            }
        }

        // 计算每个数字可以间接转化的数的个数
        for (int i = 0; i < 10; i++) {
            tag[i][i] = 1;
            for (int j = 0; j < 10; j++) {
                if (tag[i][j]) {
                    d[i]++;
                }
            }
        }

        int z = 0;
        p[0] = 1;

        // 根据输入的字符串计算结果
        for (int i = 0; a[i]; i++) {
            z = 0;
            int x = d[a[i] - '0'];

            for (int i = 0; i < 500; i++) {
                p[i] = (p[i] * x + z);
                z = p[i] / 10;
                p[i] %= 10;
            }
        }

        // 输出结果
        int i = 500;
        while (p[i] == 0) i--;

        for (; i >= 0; i--) {
            cout << p[i];
        }
        cout << endl;
    }

    return 0;
}