排列+函数映射——hdu6038好题

/*

引理：[0,n-1]的排列，i向a[i]连边，那么每个数必定在一个环中

所以数组a可以分割成一些环，数组b也可以分割成一些环

先讨论a的一个环

a[a1]=a2 a[a2]=a3 a[a3]=a4 a[a4]=a5 a[a5]=a6 a[a6]=a1 这个环长度为6

那么套到函数 f[i]=b[ f[a[i] ]中

    f[a1]=b[f[a2]]

    f[a2]=b[f[a3]]

    f[a3]=b[f[a4]]

    f[a4]=b[f[a5]]

    f[a5]=b[f[a6]]

    f[a6]=b[f[a1]]

可以把b[f[a[i]]] = f[i] 当成是b数组的下标i到b[i]的映射 ,只不过这里的下标i 是f[a[i]]], b[i] 是f[i] 
（可以发现这个f函数有点像反函数的感觉）

那么显然因为b也有和a类似的循环节，我们要找到一个b的循环节来套到上述映射里，这个循环节长度必须是上面循环节的约数


因为a[i]=ai 的循环节是6，那么b关于f的映射必定要能整除6

如果不是约数，那么f[ai]可能会对应到不同的值，这就不满足映射条件了

求方案数，设a其中一个长度为len的环的组成方案有k种，那么计算k时b所有长为len约数的环都要算上贡献

最后的结果就是 mul(k)，即所有k相乘

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

#define mod 1000000007

#define ll long long

int a[maxn],b[maxn],n,m,cnt1[maxn],cnt2[maxn],vis[maxn];

ll tot[maxn];

ll Pow(ll a,ll b){

    ll res=;

    while(b){

        if(b%)res=res*a%mod;

        b>>=;a=a*a%mod;

    }

    return res;

}

int main(){

    int t=;

    while(cin>>n>>m){

        t++;

        memset(cnt1,,sizeof cnt1);

        memset(cnt2,,sizeof cnt2);

        for(int i=;i<n;i++)scanf("%d",&a[i]);

        for(int i=;i<m;i++)scanf("%d",&b[i]);

        memset(vis,,sizeof vis);

        for(int i=;i<n;i++)

            if(!vis[i]){

                int p=i,len=;

                vis[i]=;

                while(a[p]!=i)

                    p=a[p],len++,vis[p]=;

                cnt1[len]++;

            }

        memset(vis,,sizeof vis);

        for(int i=;i<m;i++)

            if(!vis[i]){

                int p=i,len=;

                while(b[p]!=i)

                    p=b[p],len++,vis[p]=;

                cnt2[len]++;

            }

        memset(tot,,sizeof tot);

        for(int len=;len<=m;len++)//枚举b环的长度len

            for(int j=;j*len<=n;j++)

                tot[j*len]=(tot[j*len]+cnt2[len]*len%mod)%mod;

        //每个长度为len的a环都有tot[len]种安排方案

        ll ans=;

        for(int len=;len<=n;len++)

            if(cnt1[len])

                ans=ans*Pow(tot[len],cnt1[len])%mod;

        printf("Case #%d: %lld\n",t,ans);

    }

    return ;

}