Codeforces1327 D. Infinite Path（置换）

You are given a colored permutation 𝑝1,𝑝2,…,𝑝𝑛. The 𝑖-th element of the permutation has color 𝑐𝑖.

Let’s define an infinite path as infinite sequence 𝑖,𝑝[𝑖],𝑝[𝑝[𝑖]],𝑝[𝑝[𝑝[𝑖]]]… where all elements have same color (𝑐[𝑖]=𝑐[𝑝[𝑖]]=𝑐[𝑝[𝑝[𝑖]]]=…).

We can also define a multiplication of permutations 𝑎 and 𝑏 as permutation 𝑐=𝑎×𝑏 where 𝑐[𝑖]=𝑏[𝑎[𝑖]]. Moreover, we can define a power 𝑘 of permutation 𝑝 as 𝑝𝑘=𝑝×𝑝×⋯×𝑝𝑘 times.

Find the minimum 𝑘>0 such that 𝑝𝑘 has at least one infinite path (i.e. there is a position 𝑖 in 𝑝𝑘 such that the sequence starting from 𝑖 is an infinite path).

It can be proved that the answer always exists.

Input The first line contains single integer 𝑇 (1≤𝑇≤104) — the number of test cases.

Next 3𝑇 lines contain test cases — one per three lines. The first line contains single integer 𝑛 (1≤𝑛≤2⋅105) — the size of the permutation.

The second line contains 𝑛 integers 𝑝1,𝑝2,…,𝑝𝑛 (1≤𝑝𝑖≤𝑛, 𝑝𝑖≠𝑝𝑗 for 𝑖≠𝑗) — the permutation 𝑝.

The third line contains 𝑛 integers 𝑐1,𝑐2,…,𝑐𝑛 (1≤𝑐𝑖≤𝑛) — the colors of elements of the permutation.

It is guaranteed that the total sum of 𝑛 doesn’t exceed 2⋅105.

Output Print 𝑇 integers — one per test case. For each test case print minimum 𝑘>0 such that 𝑝𝑘 has at least one infinite path.

Example inputCopy 3 4 1 3 4 2 1 2 2 3 5 2 3 4 5 1 1 2 3 4 5 8 7 4 5 6 1 8 3 2 5 3 6 4 7 5 8 4 outputCopy 1 5 2 Note In the first test case, 𝑝1=𝑝=[1,3,4,2] and the sequence starting from 1: 1,𝑝[1]=1,… is an infinite path.

In the second test case, 𝑝5=[1,2,3,4,5] and it obviously contains several infinite paths.

In the third test case, 𝑝2=[3,6,1,8,7,2,5,4] and the sequence starting from 4: 4,𝑝2[4]=8,𝑝2[8]=4,… is an infinite path since 𝑐4=𝑐8=4.

在多校学习置换的时候大佬给的题，现在才开始补嘤嘤。

感觉你会了多校那个置换，这个题就很简单了。

题意： $p^2$代表将$p$数组置换成$p[p[i]]$， $p^3$代表将$p$数组置换成$p[p[p[i]]]$，以此类推

思路： 首先题目置换实际就是按照$i->p[i]->p[p[i]]->p[p[p[i]]]...$建图，这样的话会形成很多个环。

假设某个环的长度为$n$，环中节点为$a1,a2,a3...$，置换次数为$k$ 可以发现，当$k$整除$n$的时候，实际就是把这个大环分成很多个小环，当$k$不整除$n$的时候，只是改变环的顺序，数目还是没变。

因此如果$n=6,k=2$，最后形成两个长度为3的环，为： $(a1,a3,a5)$，$(a2,a4,a6)$。 如果$n=6,k=3$，最后形成三个长度为2的环，为： $(a1,a4)$,$(a2,a5)$,$(a3,a6)$。

这样你只要找到所有的环，算出其长度和真实节点结构，再枚举要其约数代表要置换多少次，然后O(n)$check$就好了。

特殊的，如果这个环本身所有对应$c$数组的值都相同，那么不需要额外置换，答案就是1。

而一个数的因数个数为分解质因数后的质因数个数加一乘积，这个数字不会很大。 所以复杂度为$nlog(n)$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include <set> #include <map> #include <queue> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; int p[maxn],c[maxn]; int fa[maxn],cnt[maxn]; int findset(int x) { if(fa[x] == x) return x; return fa[x] = findset(fa[x]); } void Union(int x,int y) { int rx = findset(x),ry = findset(y); if(rx != ry) { fa[rx] = ry; } } bool check(vector<int>vec,int num) { //环上点和间距 int n = vec.size(); for(int i = 0;i < num;i++) { //向后推num位 int flag = 1; for(int j = 0;j < n / num;j++) { // int pos = i + j * num; if(c[vec[pos]] != c[vec[i]]) { flag = 0;break; } } if(flag) return true; } return false; } int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i = 1;i <= n;i++) { fa[i] = i; cnt[i] = 0; } for(int i = 1;i <= n;i++) { scanf("%d",&p[i]); Union(i,p[i]); } for(int i = 1;i <= n;i++) { scanf("%d",&c[i]); } for(int i = 1;i <= n;i++) { cnt[findset(i)]++; } int ans = 1e9; for(int i = 1;i <= n;i++) { if(cnt[i] == 0) { continue; } int num = cnt[i]; //环的长度 if(num == 1) { ans = 1; break; } int now = i; ans = min(ans,num); vector<int>vec; for(int j = 0;j < num;j++) { //环中节点 vec.push_back(now); now = p[now]; } int flag = 1; for(int j = 0;j < vec.size();j++) { if(c[vec[j]] != c[vec[0]]) { flag = 0;break; } } if(flag) { ans = 1; break; } for(int j = 2;j <= num;j++) { //枚举约数，幂次是多少 if(num % j == 0) { if(check(vec,j)) { ans = min(ans,j);break; } } } } printf("%d\n",ans); } return 0; } //3