题解 | 恶魔果实

每个数的情况是独立的，我们只需要算出每个数能变换成多少种数字即可，这点用bfs实现，我们只需要搜索0-9的数即可

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e4+7;
//倒序不要忘记是--不是++
void solve(){
    int x,n;cin>>x>>n;
    vector<vector<int>> e(11);
    vector<vector<int>> is(11,vector<int>(11,0));
    while(n--){
        int a,b;cin>>a>>b;
        if(is[a][b]) continue;
        is[a][b]=1;
        e[a].push_back(b);
    }
    vector<int> cnt(11,0);
    for(int i=0;i<=9;i++){
        vector<bool> vis(10,false);
        queue<int> q;
        q.push(i);
        while(q.size()){
            cnt[i]++;
            vis[i]=1;
            int t=q.front();
            q.pop();
            for(auto u:e[t]){
                if(vis[u]) continue;
                vis[u]=1;
                q.push(u);
            }
        }
    }
    // for(int i=1;i<=9;i++) cout<<cnt[i]<<" ";
    // cout<<"\n";
    int ans=1;
    while(x){
        int cur=x%10;
        ans=ans*cnt[cur]%mod;
        x/=10;
    }
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}