题解 | 恶魔果实

#include<bits/stdc++.h>
#include <vector>
#define endl '\n'
using namespace std;
const int mod = 1e4+7;
bool inst[10];
vector<vector<int> > d(10);
vector<int> num(10);

int dfs(int n) {
    if(inst[n]) return 0;
    inst[n] = 1;
    if(d[n].size() == 0) return 1;
    
    int cnt = 0;
    for(int i:d[n]) {
        cnt += dfs(i);
    }
    cnt++;
    return cnt;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,x;
    cin >> x >> n;
    int a,b;
    for(int i = 1;i<=n;i++) {
        cin >> a >> b;
        d[a].emplace_back(b);
    }

    for(int i = 0;i<=9;i++) {
        num[i] = dfs(i);
        //cout << num[i] << ' ';
        for(int i = 1;i<=9;i++) {
            inst[i] = 0;
        }
    }
    //cout << endl;
    int ans = 1;
    while(x > 0) {
        int a = x%10;
        ans = ans*num[a]%mod;
        x /= 10;
    }
    cout << ans << endl;
}

跑一次dfs