题解 CF1327D 【Infinite Path】
ix35
2020-03-24 08:23:46
## CF 1327 D Infinite Path
首先，建一张有向图，从 $i$ 向 $p_i$ 连边。
容易发现，每个点的入度和出度都为 $1$，所以形成了若干个有向环。
现在来考虑 $p^k$ 的意义，设 $s$ 向后走 $k$ 步到达的点为 $t_{s,k}$，那么这个 $p^k$ 的第 $s$ 项显然就是 $t_{s,k}$，可以用归纳法证明（幂次每增加 $1$ 就代表往前走一步）。
接下来我们要做的，就是找到一个 $k$，使得每个点向走 $k$ 步后到达的点连边后，存在一个同色环，对于每个环求一遍，最后取最小值即可，我们把这个 $k$ 叫做“步长”。
首先一个结论：步长为 $k$ 可行等价于步长 $\gcd(k,l)$ 可行，其中 $l$ 是环上点的数量，这个应该不难证明。
又 $\gcd(k,l)\leq k$，所以答案一定是形如 $\gcd(k,l)$ 形式的数，即 $l$ 的因数。
所以我们只需要暴力枚举 $l$ 的每个因数并判断即可，感觉这个技巧和 NOI OL 的 T3 是相似的。
时间复杂度为 $O(n\log n)$ 左右（把 $d(n)$ 看作 $\log n$ 了）。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int t,n,m,p[MAXN],c[MAXN],vis[MAXN],ok[MAXN],nw[MAXN];
bool chk (int x,int len) {
int flg=0;
for (int i=0;i<x;i++) {
int cur=i,flg2=1;
for (int j=0;j<len/x;j++) {
if (c[nw[cur]]!=c[nw[(cur+x)%len]]) {flg2=0;break;}
cur+=x;
}
if (flg2) {flg=1;break;}
}
return flg;
}
int main () {
scanf("%d",&t);
for (int ii=1;ii<=t;ii++) {
scanf("%d",&n);
for (int i=1;i<=n;i++) {scanf("%d",&p[i]);}
for (int i=1;i<=n;i++) {scanf("%d",&c[i]);}
for (int i=1;i<=n;i++) {
if (!vis[i]) {
int cur=i,len=0;
while (!vis[cur]) {
vis[cur]=1;
nw[len++]=cur;
cur=p[cur];
}
for (int j=1;j*j<=len;j++) {
if (len%j) {continue;}
if (chk(j,len)) {ok[j]=1;}
if (chk(len/j,len)) {ok[len/j]=1;}
}
}
}
for (int i=1;i<=n;i++) {
if (ok[i]) {printf("%d\n",i);break;}
}
for (int i=1;i<=n;i++) {ok[i]=vis[i]=0;}
}
return 0;
}
```