恶魔果实

解题思路

有 n 个神奇的恶魔果实，每个恶魔果实有一个改变数字的能力，可以把数字 a 变成数字 b。
给定一个正整数 x，吃完这些恶魔果实后，可以把数字 x 变成多少种的数。
注：每一个恶魔果实的能力可以重复使用多次，当然也可以不用，存在相同能力的恶魔果实。

使用 vis 记录数字 a 可以变成的数字，并计算数字的种类 cnt。
计算整数 x 中每个数字能变成的数字个数（包括这个数字本身）。
假设 x 中有 k 个数字，第 1 个数字能变成的数字个数为 ，第 2 个为 ，...，第 k 个为 。
根据组合数学的乘法规则，最终结果即为 。

C++代码

#include<cstdio>
#include<vector>
#include<set>
#include<memory.h>
using namespace std;

int mod = 1e4+7;

set<int> trans[10];
int vis[10];

void dfs(int a){
    vis[a] = 1;
    for(auto it=trans[a].begin(); it!=trans[a].end(); ++it){
        int b = *it;
        if(!vis[b]){
            vis[b] = 1;
            dfs(b);
        }
    }
}

int main(){
    int x;
    int n;
    scanf("%d%d", &x, &n);
    int a, b;
    for(int i=0; i<n; ++i){
        scanf("%d%d", &a, &b);
        trans[a].insert(b);
    }
    long long ans = 1;
    while(x){
        int a = x % 10;
        memset(vis, 0, sizeof(vis));
        dfs(a);
        int cnt = 0;
        for(int i=0; i<10; ++i)
            cnt += vis[i];
        ans *= cnt;
        x /= 10;
    }
    ans %= mod;
    printf("%lld\n", ans);
    return 0;
}