/** 题目：hdu6038 Function 链接：http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意：给定一个a排列[0,n-1],一个b排列[0,m-1]。 定义函数f，定义域为[0,n-1],值域为[0,m-1] 请计算有多少种函数，满足f(i) = bf(ai) 对于每一个i，0<=i<=n-1; f(ai)是b排列的下标。ai表示a排列下标为i的值 两个不同的函数区分是，至少有一个i，f(i)不同于原来的f(i)'； 每一个f(i)都有一个唯一的值，表示这是一个函数。 输出结果%1e9+7; 思路： 直接拿第二组样例进行说明： 3 4 2 0 1 0 2 3 1 a0 = 2, a1 = 0, a2 = 1; b0 = 0, b1 = 2, b2 = 3, b3 = 1; f(0) = bf(2), f(2) = bf(1), f(1) = bf(0) ; 因为f(i)的值域为[0,m-1], 假设:f(2) = 0, 那么f(0) = bf(2) = b0 = 0; f(1) = bf(0) = b0 = 0; f(2) = bf(1) = b0 = 0; 最终推回来发现f(2)=0,和假设相同，所以成立。 可以发现f(2)确定值之后，f(0),f(1)也随之确定，如果成立。 假设:f(2) = 2, 同理推得, f(0) = 3, f(1) = 1, f(2) = 2.最终推回来，发现f(2)=2.和原来的假设相同。所以成立。 f(2) = 3.... 成立 f(2) = 1.... 成立。 对a排列可以建环, 0->2->1->0; 对b排列可以建环，0->0, 1->2->3->1; 由于a环0->2->1->0是0->0的整数倍，所以产生贡献1，即f(0)=f(1)=f(2)=0; 由于a环0->2->1->0是1->2->3->1的整数倍，所以产生贡献3，只要确定f(0) = 1或者2或者3， 那么f(1),f(2)也随着确定，所以三种。 最终ans = 1+3 = 4； 由于a是一个[0,n-1]排列，所以所有的数通过下标指向关系进行建图，由于每个下标只有一个唯一的值ai，该值不可能和aj相同,所以所有的图都是环。 同理b也是环。那么两边的环枚举进行长度比较，如果a中的环是b中的环的长度的整数倍，那么b中该环可以给a中该环作出贡献，贡献为b环长度。 如果b中有多个环可以给a中某个环有贡献，则累加。最终a中所有的环的贡献相乘便是答案。 */ #include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<assert.h> #include<algorithm> #include<cmath> #include<queue> using namespace std; typedef long long LL; typedef pair<int,int> P; const int mod = 1e9+7; const int N = 1e5 + 10; int visa[N]; ///visa[i]表示a中长度为i的环出现的次数。 int visb[N]; ///visb[i]表示b中长度为i的环出现的次数。 vector<P>va, vb;///从visa，visb中取出来。 int vis[N]; int pa[N], pb[N]; LL value[N]; LL Pow(LL a,LL b) { LL p = 1; while(b) { if(b&1) p = p*a%mod; a = a*a%mod; b>>=1; } return p; } int main() { int n, m, cas=1; while(scanf("%d%d",&n,&m)==2) { for(int i = 0; i < n; i++) scanf("%d",&pa[i]); for(int i = 0; i < m; i++) scanf("%d",&pb[i]); memset(visa, 0, sizeof visa); memset(vis, 0, sizeof vis); for(int i = 0; i < n; i++){ if(vis[i]==0){ int pos = i; int cnt = 1; vis[i] = 1; while(vis[pa[pos]]==0){ pos = pa[pos]; vis[pos] = 1; cnt++; } visa[cnt]++; } } memset(visb, 0, sizeof visb); memset(vis, 0, sizeof vis); for(int i = 0; i < m; i++){ if(vis[i]==0){ int pos = i; int cnt = 1; vis[i] = 1; while(vis[pb[pos]]==0){ pos = pb[pos]; vis[pos] = 1; cnt++; } visb[cnt]++; } } va.clear(); vb.clear(); for(int i = 1; i <= n; i++){ if(visa[i]==0) continue; va.push_back(P(i,visa[i])); } for(int i = 1; i <= m; i++){ if(visb[i]==0) continue; vb.push_back(P(i,visb[i])); } for(int i = 0; i < va.size(); i++){ value[i] = 0; for(int j = 0; j < vb.size(); j++){ if(va[i].first%vb[j].first==0){ value[i] += vb[j].first*vb[j].second; } } } LL ans = 1; for(int i = 0; i < va.size(); i++){ if(value[i]==0){ ans = 0; break; } ans = ans*Pow((LL)value[i],(LL)va[i].second)%mod; } printf("Case #%d: %lld ",cas++,ans); } return 0; }