算法

(floyd+高精)

1. 简历一张图，计算任意两个数字之间的传递闭包
2. 统计从每个点可以变换到那些其他点的个数
3. 乘法原理，注意高精度乘法

C++ 代码

#include <bits/stdc++.h>

int cnt[10]; 
bool vis[10][10];

struct BigNum {
    int num[100], len;
    void init() {
        memset(num, 0, sizeof(num));
        len = 0;
    }
};

BigNum Multi(BigNum &x, BigNum &y) {
    BigNum z;
    z.init();
    z.len = x.len + y.len;
    for (int i = 0; i < x.len; ++i)
        for (int j = 0; j < y.len; ++j)
            z.num[i + j] += x.num[i] * y.num[j];
    for (int i = 0; i < z.len; ++i) {
        z.num[i + 1] += z.num[i] / 10;
        z.num[i] %= 10;
    }  
    while (z.len > 1 && !z.num[z.len - 1]) --z.len;
    return z;
}

int main() {
    std::string n;
    int k;
    std::cin >> n >> k;

    for (int i = 0;i < k; ++i) {
        int x, y;
        std::cin >> x >> y;
        vis[x][y] = true; 
    }

    for (int i = 0; i < 10; ++i) vis[i][i] = true;

    for (int k = 0; k < 10; ++k) {
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 10; ++j) {
                vis[i][j] = vis[i][j] || (vis[i][k] && vis[k][j]);
            }
        }
    }

    // 记录每一个数有几种变换可能 
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (vis[i][j]) cnt[i]++;
        }
    }

    BigNum ans;
    ans.num[0] = 1; 
    ans.len = 1;
    for (int i = 0; n[i]; ++i) {
        int cur = n[i] - '0';
        int x = cnt[cur];
        BigNum tmp;
        tmp.init();
        while (x > 0) {
            tmp.num[tmp.len++] = x % 10;
            x /= 10;
        }
        ans = Multi(ans, tmp);
    }

    for (int i = ans.len - 1; i >= 0; --i) std::cout << ans.num[i];

    return 0;
}