题解 | 恶魔果实

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod = 1e4+7;
typedef long long ll;
typedef unsigned long long ull;
ll n,x;
int cnt[10];


bool vis[10][10];


void floyed()
{
    for(int k=0;k<=9;k++)
    {
        for(int i=0;i<=9;i++)
        {
            for(int j=0;j<=9;j++)
            {
                vis[i][j] |= vis[i][k]&vis[k][j]; 
            }
        }
    }
}


ll qpow(ll a,ll b,ll p)
{
    ll res = 1;
    for(;b;b>>=1)
    {
        if(b&1)
        {
            res = res*a%p;
        }
        a = a*a%p;
    }
    return res;
}

void solve()
{
    cin>>x>>n;
    ll x2 = x;
    while(x2)
    {
        cnt[x2%10]++;
        x2/=10;
    }

    for(int i=1;i<=n;i++)
    {
        int xx,yy;
        cin>>xx>>yy;
        vis[xx][yy]=1;
    }
    floyed();


    // for(int i=0;i<=9;i++)
    // {
    //     for(int j=0;j<=9;j++)
    //     {
    //         cout<<vis[i][j]<<' ';
    //     }
    //     cout<<'\n';
    // }
    ll res = 1;

    for(int i=0;i<=9;i++)
    {
        int ct = 0;
        for(int j=0;j<=9;j++)
        {
            if(i==j)continue;
            if(vis[i][j])ct++;
        }
        res = res*qpow(ct+1,cnt[i],mod)%mod;
    }
    cout<<res<<'\n';

    

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();

    }


    return 0;
}

小诈骗题，数据量很小可以建图使用floyed判断是否到达i到j