hdu 6038 | 2017 Multi-University Training Contest - Team 1 E Function (置换群找循环节)
http://acm.hdu.edu.cn/showproblem.php?pid=6038
题意：
给出两个序列 a 和 b ，求满足 f[i]= b_{f[a[i]]} 的函数个数。
思路：
分别找两个序列的循环节，这一点是比较容易想到的。
由于点都在0..n-1 或者0..m-1，因此没必要建图跑dfs找循环节，直接while就可以了。
然后发现一个循环节如果符合条件，那么对答案的贡献是循环节长度。
但是没有想清楚，什么才是符合条件的循环节。
结论是，b的循环节长度当且近当是A的循环节的长度的因子时，b的这个循环节会对答案贡献其长度的大小。
对于A的每个循环节，都是互不影响的。
而且我们只关心循环节的长度。
因此O（n）和O(m)的时间，处理出所有循环节的长度。
然后分别枚举累计答案即可。
但是我怎么感觉。。。这复杂度不太对啊。。。。
对于O(1E5)的序列。。我好像可以构造出1E5个长度为1的循环节？
那么1E5 * 1E5,1E10的复杂度了。。。
然而看了下官方题解。。。发现给出的复杂度分析是O(n+m)
？？？？？？？？？？？？？？？？？？？？？
所以这是说。。。数据保证O(n*m) < O (n+m)了么。。。
这是面向数据解题。。还是说我哪里想错了啊。。。orz
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月01日 星期三 14时17分58秒
4File Name :6038.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=1E5+7;
24const LL mod = 1E9+7;
25int a[N],b[N];
26bool vis[N];
27int n,m;
28vector <int>loopa,loopb;
29vector <int> findloop( int *a,int n)
30{
31 vector<int>res;
32 ms(vis,false);
33 for ( int i = 0 ; i < n ; i++)
34 {
35 int cur = i ;
36 if (vis[cur]) continue;
37 int len = 0;
38 while (!vis[cur])
39 {
40 // cout<<"cur:"<<cur<<endl;
41 vis[cur] = true;
42 cur = a[cur];
43 len++;
44 }
45 res.PB(len); //只关心循环节的长度
46 }
47 return res;
48}
49int main()
50{
51 #ifndef ONLINE_JUDGE
52 freopen("./in.txt","r",stdin);
53 #endif
54 int cas = 0 ;
55 while (~scanf("%d %d",&n,&m))
56 {
57 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i);
58 for ( int i = 0 ; i < m ; i++) scanf("%d",b+i);
59 loopa.clear();
60 loopb.clear();
61 loopa = findloop(a,n);
62 loopb = findloop(b,m);
63
64 int lena = loopa.size();
65 int lenb = loopb.size();
66 //cout<<"lena:"<<lena<<" lenb:"<<lenb<<endl;
67 LL ans = 1;
68 for ( int i = 0 ; i < lena ; i++)
69 {
70 LL tmp = 0 ;
71 for ( int j = 0 ; j < lenb ; j++)
72 {
73 // cout<<"i:"<<i<<" j:"<<j<<" loopb[j]:"<<loopb[j]<<endl;
74 if (loopa[i]%loopb[j]==0) tmp = (tmp + loopb[j])%mod;
75 }
76 ans = ans * tmp % mod;
77 }
78 printf("Case #%d: %lld\n",++cas,ans);
79 }
80
81 #ifndef ONLINE_JUDGE
82 fclose(stdin);
83 #endif
84 return 0;
85}