CodeForces - 1327D Infinite Path(图论综合)
题目链接：点击查看
题目大意：首先给出一个 1 ~ n 的排列，用 p 数组表示，再给出给个点的颜色，用 c 数组表示
然后抛出Infinite Path的定义：对于某个 i ，p[ i ] , p[ p[ i ] ] , p[ p[ p[ i ] ] ] 无限嵌套下去，且每个位置的颜色相同，即 c[ i ] = c[ p[ i ] ] = c[ p[ p[ i ] ] ] = c[ p[ p[ p[ i ] ] ] ] 等等等等
下面重载一下排列的乘法运算，假如 a 和 b 是 1 ~ n 的两个排列，那么 a * b = b[ a[ i ] ] ，a * a = a[ a [ i ] ]
从而重载一下排列的乘方运算，p^k = p * p * p ... * p ( k 个 p )
题目要求我们找到一个最小的 k ，使得给出的排列 p 的 k 次方，存在一个 i ，可以满足上述的Infinite Path
题目分析：读完题后，不难想到如果想要找到Infinite Path的话，必然是一个循环，而 1 ~ n 的一个排列，如果转换为有向图的形式，可以视为数个不相交的有向环，之前做题记住的结论，忘记是怎么证明的了，这样就可以将给出的排列 p 以有向图的形式表示，接下来结合前几周离散数学新学到的知识（学以致用）
可以将 p^k 这个抽象的概念具体化，简单来说，p^k 就是在 p 这个有向图中，经过长度为 k 的步长可以到达的关系
再换句话说，p^k 就是在环中将距离相隔为 k 的数个点按照原次序重新组合成一个新的环
如果上面这句话不好理解的话，对于题目给出的第三个样例画一下图就好理解了
综上所述，现在题目就转换为了，在数列 p 的所有环中，能否找到一个等差 k ，使得环上所有满足等差关系的位置：pos , pos + k , pos + 2 * k , pos + 3 * k 等等位置的颜色相同，维护这个最小的 k 就是答案了
到此为止这个题目剩下的就是实现了，比赛的时候明明已经到了这一步，却卡在了如何在环上找到等差的位置这里，不会实现，还是自己太菜了啊，赛后看了大佬的代码发现只需要nlogn维护因子就好了，因为如果想满足在环上满足等差，那么这个差值 k 一定是环的长度的因子，对于每个长度的因子，nlogn预处理一下就可以了
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
作者：Frozen_Guardian
