526互联

【补题记录】 Codeforces Round 797 (Div. 3) F Shifting String（置换环）

发布时间 2023-07-05 22:51:07作者: komushdjk

思路：

根据这个排列进行替换的操作可以往置换环考虑，就是对于每一段字串，它的变换都是有规律的，经过一定的操作之后都会回到原点，可以想象转化成图上问题。

参考ygg的题解，直接用链表模拟这个转化的过程，然后暴力计数，因为要满足所有点都回到对应原位，所以求所有满足条件的长度之后求lcm即可

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N = 200+10,mod = 1e9+7;

int p[N];
bool v[N];
vector<int> c;
void dfs(int x){//找到完整的一个环并且存在vector c中
	if(v[x])return;
	v[x] = 1;
	c.push_back(x);
	dfs(p[x]);
}
void solve() {
	int n;
	string s;
	cin >> n >> s;
	s = " " + s;
	for(int i = 1; i <= n; i ++) cin >> p[i],v[i] = 0;
	int res = 1;
	for(int i = 1; i <= n; i ++){
		if(!v[i]){
			c.clear();
			dfs(i);
			list<char> pres,nows;
//			for(int j = i; v[j]; v[j] = 1, j = p[j])
//				pres.push_back(s[j]);
			for(auto id: c) pres.push_back(s[id]);
			nows = pres;
			nows.push_back(nows.front());//把头结点移动到尾部，就是模拟这个环上的点移动的过程
			nows.pop_front();
			int t = 1;
			while(pres != nows){
				nows.push_back(nows.front());
				nows.pop_front();
				t ++;//不断重复上述操作然后计数
			}
			res = res * t /__gcd(res,t);
		}
	}
	
	cout << res <<'\n';

}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _t = 1;
	cin >> _t;
	while(_t --)
		solve();
	
	return 0;
}