题目传送门 首先容易发现初始给的点之间相互跳跃,把图分成了一个或多个环. 环中的点再怎么跳也跳不出环. 对于位置i,他的初始值为 p 1 [ i ] p_1[i] p1[i], p k [ i ] p_k[i] pk[i]的值就要在环中找了. 对于一个长度为m的环, p k [ c [ i ] ] p_k[c[i]] pk[c[i]]= c [ ( i + k ) % m ] c[(i+k)\%m] c[(i+k)%m] 0 < = i < m _{0<=i<m} 0<=i<m 方 便 取 模 运 算 _{方便取模运算} 方便取模运算 那么显然要形成一个更小的环,k必须是m的因子. 对于每个因子,检查该小环上的颜色是否相同即可.
#include<bits/stdc++.h> using namespace std; #define fore(i, l, r) for(int i = int(l); i < int(r); i++) const int INF = int(1e9); int n; vector<int> p, c; inline bool read() { if(!(cin >> n)) return false; p.resize(n); c.resize(n); fore(i, 0, n) { cin >> p[i]; p[i]--; } fore(i, 0, n) cin >> c[i]; return true; } inline void solve() { vector<int> used(n, 0); int ans=n; fore(st,0,n) { if(used[st])continue; vector<int>cycle; int dex=st; while(!used[dex]) { cycle.push_back(dex); used[dex]=1; dex=p[dex]; } int size=cycle.size(); fore(s,1,size+1) { if(size%s)continue; fore(h,0,s) { bool check=true; int col=c[cycle[h]]; for(int t=h+s;t<size;t+=s) { if(c[cycle[t]]!=col) check= false; } if(check) ans=min(ans,s); } } } cout << ans << endl; } int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif int t; cin >> t; while(t--) { read(); solve(); } return 0; }