前置知识
轮换求置换的阶
例如 由1 2 3 4 5 变为 1 3 2 5 4可以写出其两个转换 (1 3 2)(4 5 ),在同一个转换中的数字经过循环可以回到他们对应的原位置。置换的阶即为所有轮换阶数的最小公倍数(lcm)。
一组数据的最小公倍数,可以依次求元素和当前最小公倍数的最小公倍数,最后的最小公倍数即为整组数据的最小公倍数。
// #pragma GCC optimize (2)
// #pragma G++ optimize (2)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define endl '\n'
#define int long long
#define lowbit(x) x &(-x)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TLE(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int gcd(int a,int b)
{
return b ? gcd (b, a % b) : a;
}
int lcm(int a,int b)
{
return a / gcd(a,b) * b;
}
char s[2000];int p[N];
bool vis[N];
void solve()
{
int n;
cin>>n;
cin>>s;
for(int i=1;i<=n;i++)vis[i]=false;
rep(i,0,n-1)
{
cin>>p[i];
p[i]--;
}
int ans=1;
rep(i,0,n-1)
{
if (vis[i]) continue;
vis[i] = true;
int u = p[i];
string t = string (1, s[i]);
while (u != i) //获取一个轮换子序列
{
vis[u] = true;
t += s[u];
u = p[u];
}
int cnt=(t+t).find(t,1);//求得当前轮换的阶数
ans=lcm(ans,cnt);
}
cout<<ans<<endl;
return;
}
signed main()
{
TLE();
int T;
//T = 1;
cin>>T;
while (T--)
solve();
return 0;
}