牛客tracker2026.03.02恶魔果实 存图 + bfs

恶魔果实

现在有个能力，每次可以把数字a变成数字b，并且这个使用是没有限制的可以是零次也可以是多次。
给出一个数字x。问，最终可以把x变成多少种不同的数。

根据样例，我们可以得到这个变化其实是每一个个位数有可能出现的变化，最后乘到一起。
比如一个两位数，第1位可以变化4次，第2位可以变化2次，那么最终变化出来的总数应该是4×2=8种。
但是这个变化有可能是多岔路的形式，比如对一个数字4，可以4->5->6，也可以4->7->8。所以最后这一位的变化数应该是3+2=5种(4出现了两次第二次不算贡献）。
那么就启发了可以类似单向边存图，跑一遍bfs就可以了。

#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;
}