题解 | 恶魔果实

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e4+7;
const int N = 1e6+100;
int f[10][10];
int vis[10];
int main()
{
    int x,n;
    cin>>x>>n;
    for(int i = 1 ; i <= n ; ++i)
    {
        int a,b;cin>>a>>b;
        f[a][b] = 1;
    }
    int ans = 1;
    while(x)
    {
        for(int i = 0 ; i <= 9 ; ++i)vis[i] = 0;
        queue<int>q;
        int now = x%10;x /= 10;
        q.push(now);
        int cnt = 0;
        while(q.size())
        {
            now = q.front();q.pop();
            if(vis[now] == 1)continue;
            vis[now] = 1;cnt++;
            for(int i = 0 ; i <= 9 ; ++i)
            {
                if(i == now)continue;
                if(f[now][i] == 1 && vis[i] == 0)q.push(i);
            }
        }
        ans = ans*cnt%mod;
    }
    // ans = (ans%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}

现在有个能力，每次可以把数字a变成数字b，并且这个使用是没有限制的可以是零次也可以是多次。

给出一个数字x。问，最终可以把x变成多少种不同的数。

根据样例，我们可以得到这个变化其实是每一个个位数有可能出现的变化，最后乘到一起。

比如一个两位数，第1位可以变化4次，第2位可以变化2次，那么最终变化出来的总数应该是4×2=8种。

但是这个变化有可能是多岔路的形式，比如对一个数字4，可以4->5->6，也可以4->7->8。所以最后这一位的变化数应该是3+2=5种(4出现了两次第二次不算贡献）。

那么就启发了可以类似单向边存图，跑一遍bfs就可以了。