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