题意

a是一个0到n-1的集合，b是一个0到m-1的集合。
计算有多少种不同的从a到b的映射f，满足$f(i)=b_{f(a_i)}$答案对1000000007取模。

思路

观察方程可以发现,如果在b中有一个置换，且循环节长度为c，那么取a中的某个值映射到b中，便可以确定c个a中的值到b中值的映射关系。
如果a中有p个置换，每个置换的循环节长度为$p_i$,那么它只能和在b中循环节长度为$p_i$的因数的置换进行映射（如果不这样，会使a中的值有多个b中的值对应）。
因此，我们只需要算出对于a中的每个循环节的长度，在b中的循环节中有多少个因数就能算出答案了。
我们直接算是$O(n^2)$的时间复杂度，会超时。所以需要开个数组$cnt[i]$记录一下b中的循环节长度为i的个数。然后遍历a中的循环节就能在规定时间内算出答案。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1000000+10;
#define OJ
//#define Now
#ifdef Now
typedef long long ll;
#endif
#ifdef OJ
typedef __int64 ll;
#endif

const ll mod=1000000007;
int a[Nmax];
int b[Nmax];
int n,m;
vector<ll> moda;
int book[Nmax];
ll cnt[Nmax];
int main()
{
    #ifdef test
    #endif
#ifdef Now
    freopen("f.in","r",stdin);
#endif
    int ttt=0;
    while(~scanf("%d%d",&n,&m))
    {
        ttt++;
        moda.clear();
        //modb.clear();
        for(int i=0;i<Nmax;i++)
            cnt[i]=0;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int j=0;j<m;j++)
            scanf("%d",&b[j]);
        for(int i=0;i<=n;i++)
            book[i]=0;
        for(int i=0;i<n;i++)
        {
            if(book[i])
                continue;
            int j=i;
            ll t=0;
            while(!book[j])
            {
                book[j]=1;
                t++;
                j=a[j];
            }
            moda.push_back(t);
        }
        for(int i=0;i<=m;i++)
            book[i]=0;
        for(int i=0;i<m;i++)
        {
            if(book[i])
                continue;
            int j=i;
            ll t=0;
            while(!book[j])
            {
                book[j]=1;
                t++;
                j=b[j];
            }
            cnt[t]++;
        }
        int nn=moda.size();
        //for(int i=0;i<mm;i++)
            //cnt[modb[i]]++;

        //for(int i=0;i<=3;i++)
            //printf("cnt[%d]:%d\n",i,cnt[i]);
        ll ans=1;
        for(int i=0;i<nn;i++)
        {
            ll num=moda[i];
            ll now=0;
            for(int j=1;j<=num;j++)
            {
                if(cnt[j])
                {
                    if(num%j==0)
                    {
                        now=(now+j*cnt[j])%mod;
                    }
                }
            }
            //if(num==1)
                //now=cnt[1]%mod;
            //else
                //now=(cnt[1]+num*cnt[num]%mod)%mod;
            ans=(ans*now)%mod;
        }
        while(ans<0)
            ans+=mod;
#ifdef Now
        printf("Case #%d: %lld\n",ttt,ans);
#endif
#ifdef OJ
        printf("Case #%d: %I64d\n",ttt,ans);
#endif
    }
    return 0;
}