排列+函数映射——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=1; while(b){ if(b%2)res=res*a%mod; b>>=1;a=a*a%mod; } return res; } int main(){ int t=0; while(cin>>n>>m){ t++; memset(cnt1,0,sizeof cnt1); memset(cnt2,0,sizeof cnt2); for(int i=0;i<n;i++)scanf("%d",&a[i]); for(int i=0;i<m;i++)scanf("%d",&b[i]); memset(vis,0,sizeof vis); for(int i=0;i<n;i++) if(!vis[i]){ int p=i,len=1; vis[i]=1; while(a[p]!=i) p=a[p],len++,vis[p]=1; cnt1[len]++; } memset(vis,0,sizeof vis); for(int i=0;i<m;i++) if(!vis[i]){ int p=i,len=1; while(b[p]!=i) p=b[p],len++,vis[p]=1; cnt2[len]++; } memset(tot,0,sizeof tot); for(int len=1;len<=m;len++)//枚举b环的长度len for(int j=1;j*len<=n;j++) tot[j*len]=(tot[j*len]+cnt2[len]*len%mod)%mod; //每个长度为len的a环都有tot[len]种安排方案 ll ans=1; for(int len=1;len<=n;len++) if(cnt1[len]) ans=ans*Pow(tot[len],cnt1[len])%mod; printf("Case #%d: %lld\n",t,ans); } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/11191195.html