Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1610 Accepted Submission(s): 755
Problem Description
You are given a permutation a from 0 to n−1 and a permutation b from 0 to m−1.
Define that the domain of function f is the set of integers from 0 to n−1, and the range of it is the set of integers from 0 to m−1.
Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i from 0 to n−1.
Two functions are different if and only if there exists at least one integer from 0 to n−1 mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo 1e9+7.
Define that the domain of function f is the set of integers from 0 to n−1, and the range of it is the set of integers from 0 to m−1.
Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i from 0 to n−1.
Two functions are different if and only if there exists at least one integer from 0 to n−1 mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo 1e9+7.
Input
The input contains multiple test cases.
For each case:
The first line contains two numbers n, m. (1≤n≤100000,1≤m≤100000)
The second line contains n numbers, ranged from 0 to n−1, the i-th number of which represents ai−1.
The third line contains m numbers, ranged from 0 to m−1, the i-th number of which represents bi−1.
It is guaranteed that ∑n≤1e6, ∑m≤1e6.
For each case:
The first line contains two numbers n, m. (1≤n≤100000,1≤m≤100000)
The second line contains n numbers, ranged from 0 to n−1, the i-th number of which represents ai−1.
The third line contains m numbers, ranged from 0 to m−1, the i-th number of which represents bi−1.
It is guaranteed that ∑n≤1e6, ∑m≤1e6.
Output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.
Sample Input
3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1
Sample Output
Case #1: 4 Case #2: 4
题目大意：给你数列a，b，然后它们之间有函数关系f(i)=bf(ai) ，求满足要求的映射关系的个数。
思路：如果把f(ai)按照上述函数扩展下去，发现它是循环的，并且a的循环一定是b的循环的整倍数， 那么就可以跑dfs求出a和b的循环节（以及相等循环节的个数），最后求和即可。
AC代码：
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int MOD=1e9+7; const int MAXN=100010; int a[MAXN],b[MAXN]; int la[MAXN],lb[MAXN]; bool vis[MAXN]; void dfsa(int t, int l, int *num){ if(vis[t]){ la[l]++; return; } vis[t]=1; dfsa(num[t], l+1, num); } void dfsb(int t, int l, int *num){ if(vis[t]){ lb[l]++; return; } vis[t]=1; dfsb(num[t], l+1, num); } int main() { int n,m,t=0; while(~scanf("%d%d", &n, &m)) { for(int i=0;i<n;i++) scanf("%d", a+i); for(int j=0;j<m;j++) scanf("%d", b+j); memset(la, 0, sizeof(la)); memset(lb, 0, sizeof(lb)); memset(vis, 0, sizeof(vis)); for(int i=0;i<n;i++) if(!vis[i]) dfsa(i, 0, a); memset(vis, 0, sizeof(vis)); for(int i=0;i<m;i++) if(!vis[i]) dfsb(i, 0, b); int res=1; for(int i=1;i<=n;i++){ if(la[i]){ int k=(int)(sqrt(i*1.0)+0.5),tmp=0; for(int j=1;j<=k;j++){ if(i%j==0){ tmp=(tmp+lb[j]*j%MOD)%MOD; if(j*j!=i) tmp=(tmp+lb[i/j]*(i/j)%MOD)%MOD; } } for(int j=0;j<la[i];j++) res=res*tmp%MOD; } } printf("Case #%d: %d ", ++t, res); } return 0; }
嗯，是个图论题。