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
/* ***********************************************
Author :111qqz
Created Time :2017年11月01日 星期三 14时17分58秒
File Name :6038.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7const LL mod = 1E9+7;
8int a[N],b[N];
9bool vis[N];
10int n,m;
11vector <int>loopa,loopb;
12vector <int> findloop( int *a,int n)
13{
14 vector<int>res;
15 ms(vis,false);
16 for ( int i = 0 ; i < n ; i++)
17 {
18 int cur = i ;
19 if (vis[cur]) continue;
20 int len = 0;
21 while (!vis[cur])
22 {
23 // cout<<"cur:"<<cur<<endl;
24 vis[cur] = true;
25 cur = a[cur];
26 len++;
27 }
28 res.PB(len); //只关心循环节的长度
29 }
30 return res;
31}
32int main()
33{
34 #ifndef ONLINE_JUDGE
35 freopen("./in.txt","r",stdin);
36 #endif
37 int cas = 0 ;
38 while (~scanf("%d %d",&n,&m))
39 {
40 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i);
41 for ( int i = 0 ; i < m ; i++) scanf("%d",b+i);
42 loopa.clear();
43 loopb.clear();
44 loopa = findloop(a,n);
45 loopb = findloop(b,m);
1 int lena = loopa.size();
2 int lenb = loopb.size();
3 //cout<<"lena:"<<lena<<" lenb:"<<lenb<<endl;
4 LL ans = 1;
5 for ( int i = 0 ; i < lena ; i++)
6 {
7 LL tmp = 0 ;
8 for ( int j = 0 ; j < lenb ; j++)
9 {
10 // cout<<"i:"<<i<<" j:"<<j<<" loopb[j]:"<<loopb[j]<<endl;
11 if (loopa[i]%loopb[j]==0) tmp = (tmp + loopb[j])%mod;
12 }
13 ans = ans * tmp % mod;
14 }
15 printf("Case #%d: %lld\n",++cas,ans);
16 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}