题解 | 恶魔果实

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e4 + 7;

signed main() {

    int x, n;
    cin >> x >> n;
    vector<vector<bool>>to(10, vector<bool>(10, false));
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        to[a][b] = true;
    }
    for (int i = 0; i <= 9; i++) {
        to[i][i] = true;
    }
    for (int i = 0; i <= 9; i++) {
        for (int k = 0; k <= 9; k++) {
            for (int j = 0; j <= 9; j++) {
                if (to[i][k] && to[k][j]) {
                    to[i][j] = true;
                }
            }
        }
    }
    //vector<int>shu(9);
    vector<int>shu(10);//0-9是十个数
    int ans = 1;
    for (int i = 0; i <= 9; i++) {
        int cnt = 0;
        for (int j = 0; j <= 9; j++) {
            if (to[i][j]) cnt++;
        }
        //ans = (ans * cnt) % mod;
        shu[i] = cnt;
    }
    //cout << ans;
    while (x) {
        ans = (ans * shu[x % 10]) % mod;
        x /= 10;
    }
    cout << ans << endl;;
    return 0;
}