关于置换

根据《数学奥林匹克小丛书·组合数学》上关于置换的定义：

给定集合 \(X = \{1,2,3,\ldots ,n \}\)，置换 \(\varphi\) 是从 \(X\) 到 \(X\) 上的一一映射，通常记为 \[ \varphi = \begin{Bmatrix} 1 & 2 & \ldots & n \\ \varphi(1) & \varphi(2) & \ldots & \varphi(n) \end{Bmatrix} \]

由于是一一映射，所以这实际上是 \([1,n]\) 的一个排列，满足 \(\varphi(i) = i\) 的 \(i\) 成为 \(\varphi\) 的一个不动点。

直接感受就是，加了一堆概念得到的还只是一个排列，这么吃力不讨好的事情有啥用？但是看到这题题面之后就应该明白，「置换」本质上是一一映射，所以你可以用置换 \(\varphi\) 再把 \(\varphi\) 映射一遍……

而对于「不动点」，无论如何用 \(\varphi\) 去映射，都不会改变这些元素的值。（知道这个说不定能骗点分）。

关于置换的一些性质、题目和解题方法，刘汝佳的《入门经典训练指南》上还有所涉及。

分析

题意很简单，然而我一开始完全没有思路。注意到如果 \(A\) 中存在不动点，那么只要检查是否与 \(B\) 的对应位置相同即可。

手算不难发现对于一个 \(i\)，从 \(a_i\) 不断映射直到 \(a_i' = i\)，经过的数字构成了一个环，含义是无论怎么置换都会如此循环。把环中数组当作下标，把 \(A\) 中对应的以元素列出来，记为 \(p\)。能够发现正好相差一位（因为 \(A\) 把 \([1,n]\) 映射了一次了）。如果其中不包含 \(b_i\)，那么必然无解。同时也把 \(B\) 中对应的元素列出来，记为 \(q\)。判断从 \(p_{x} = b_i\) 的 \(x\) 开始检查 \(p\) 与 \(q\) 是否完全相同，否则无解。

假设从 \(i\) 开始置换 \(r_i\) 次才能让 \(a_i\) 变成 \(b_i\)，其环长为 \(m_i\)。由于循环节的存在，最终的 \(k\) 必定满足 \[ \begin{cases} k &\equiv r_1 \pmod {m_1} \\ k &\equiv r_2 \pmod {m_2} \\ & \vdots \\ k & \equiv r_n \pmod {m_n} \end{cases} \] 此时的 \(n\) 为环的个数。

用扩展中国剩余定理判断是否有解即可。

注意爆 long long。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define pb push_back
const int N=1e5+5;
int t, n, R, M, a[N], b[N];
bool v[N];
vector<int> r, m, c;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int exgcd(int a,int b,int& x,int& y) {
	if(!b) { x=1, y=0; return a; }
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
bool exCRT(int n) {
    // n为环的个数
	R=r[0], M=m[0];
	for(int i=1;i<n;++i) {
		int d=r[i]-R, g, mod, x, y;
		g=exgcd(M,m[i],x,y);
		if(d%g) return 0;
		mod=m[i]/g;
		x=((x*d/g)%mod+mod)%mod;
		R=x*M+R;
		M=M/g*m[i];
	}
	return 1;
}
void solve() {
	n=read();
	r.clear(), m.clear();
	memset(v,0,sizeof(v));
	for(int i=0;i<n;++i) a[i]=read()-1;
	for(int i=0;i<n;++i) b[i]=read()-1;
	for(int i=0;i<n;++i) {
		if(a[i]==i&&b[i]!=i) { puts("No"); return; }
	}
	for(int i=0;i<n;++i) {
		if(v[i]) continue;
		v[i]=1;
		int cur=a[i];
		c.clear();
		c.pb(i);
        // 起点
		while(cur!=i) {
			c.pb(cur);
			v[cur]=1;
			cur=a[cur];
		}
		vector<int> p, q;
		for(auto x:c) p.pb(a[x]), q.pb(b[x]);
		bool fg=0;
		int sz=p.size();
		for(int j=0;j<sz;++j) {
			if(p[j]==q[0]) {
                // q[0]=b[i]，置换j次才成为b[i]
				fg=1;
				for(int k=j,pos=0;k<j+sz;++k,++pos) {
					if(p[k%sz]!=q[pos]) { puts("No"); return; }
				}
				r.pb(j), m.pb(sz);
                // sz是环长
				break;
			}
		}
		if(!fg) { puts("No"); return; }
	}
	if(!exCRT(r.size())) puts("No"); else puts("Yes");
}
signed main() {
	t=read();
	while(t--) solve();
}