传送门
文章目录
题意：
懒得写了，直接贴图了。
思路：
遇事不决画成图，考虑将iii向p[i]p[i]p[i]连一个边，可以发现每个点入度为111，出度为111，所以画出来是若干个环，比如说样例三画出来就是这样的(这里只画了一个环)
上图为p1p^1p1的情况，进而可以发现，当ppp的幂次为kkk的时候，就是将每个数与其往下数kkk个数之间连边，比如p2p^2p2的图如下所示：
所以我们假设环的长度为lenlenlen，那么可以发现只有lenmodk=0len\bmod k=0lenmodk=0的kkk才有意义，其他的连边方式都是kkk的某种情况，所以我们只需要枚举lenlenlen的因子，让后判断posmoddiverpos\bmod diverposmoddiver相同的位置颜色是否一样就好了，取一个最小的因子即可。
这里写的麻烦了，完全可以用筛法替代我这个垃圾写法。
复杂度O(nn)O(n\sqrt n)O(nn)。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=200010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int a
[N
],p
[N
],c
[N
],col
[N
],cnt
[N
];
bool st
[N
];
vector
<int>v
,diver
;int solve() {int len
=v
.size();diver
.clear();for(int i
=1;i
<=len
/i
;i
++) {if(len
%i
==0) {diver
.pb(i
);if(1ll*i
*i
!=len
) diver
.pb(len
/i
);}}int ans
=INF
;for(auto x
:diver
) {for(int i
=0;i
<v
.size();i
++) cnt
[i
%x
]=len
/x
;for(int i
=0;i
<v
.size();i
++) {if(col
[i
%x
]==-1) col
[i
%x
]=c
[v
[i
]];else if(col
[i
%x
]!=c
[v
[i
]]) cnt
[i
%x
]--;}for(int i
=0;i
<v
.size();i
++) if(cnt
[i
%x
]==len
/x
) ans
=min(ans
,x
);for(int i
=0;i
<v
.size();i
++) col
[i
%x
]=-1;}return ans
;
}int main()
{
memset(col
,-1,sizeof(col
));int _
; scanf("%d",&_
);while(_
--) {scanf("%d",&n
);for(int i
=1;i
<=n
;i
++) scanf("%d",&p
[i
]),st
[i
]=0;for(int i
=1;i
<=n
;i
++) scanf("%d",&c
[i
]);int ans
=INF
;for(int i
=1;i
<=n
;i
++) if(!st
[i
]&&!st
[p
[i
]]) {if(i
==p
[i
]) {ans
=1; break;}v
.clear();v
.pb(i
); v
.pb(p
[i
]); st
[i
]=1; st
[p
[i
]]=1;int now
=p
[p
[i
]];while(!st
[now
]) {v
.pb(now
);st
[now
]=1;now
=p
[now
];}int len
=v
.size();ans
=min(ans
,solve());}printf("%d\n",ans
);}return 0;
}
总结
以上是生活随笔为你收集整理的Educational Codeforces Round 84 (Rated for Div. 2) D. Infinite Path 构建环 + 思维的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
