\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\)
解法
1回の操作で
\(A\) の \(i,j\) の部分を swap して， 同時に \(B\) の \(i,k\) の部分を swap する．
一致できるかどうかだけが問題なので， \(A\) を固定して \(B\) だけの操作にしてもよい． よって， \(A\) の swap は \(B\) の swap で置き換えができるから， 1回の操作は
\(B\) を 2回 swap する
と言い換えが出来る．
一致させるための必要条件を考えると， まず \(A,B\) は multiset として一致している必要がある． 以下，multiset として一致していると仮定する． 次に場合分けをする．
- \(A\) の元が全て異なる場合:
\(sgn(A)\) と \(sgn(B)\) が一致するのが必要十分． - \(A\) の中に等しい元がある場合:
一旦，\(A\) における等しい元を区別した順列を \(A,A'\) と書けば，\(sgn(A) \neq sgn(A')\) ． よって，\(B\) から \(A, A'\) のいずれかに一致させることが 常に可能．
実装
Multiset の判定
Multiset としての一致は，sort と unique を用いて調べることが可能．
\(sgn(A)\) の計算: \(O(N)\)
\(N := \lvert A \rvert\) とおく． 今回は順列\(A\) に対して \(sgn(A)\) が欲しいのであって，転倒数は不要． \(sgn(A)\) は \(O(N)\) で計算が可能． (\(A\) のサイクルの個数) + \(N\) \(\equiv 0\) mod \(2\) が \(sgn(A) = 1\) と同値． なぜなら，\(A\) に一つ互換を追加するとサイクルの個数が \(+1 \) or \(-1\) されるため， mod \(2\) では \(+1\) となることと， identity は サイクルが \(N\) 個であることから従う．
よって，サイクルの個数を調べればよいが，これは \(O(N)\) で可能．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// a is a permutation
// return 0 if a is an even permutation
// return 1 if a is an odd permutation
bool f(vll a){
ll ret = 0;
ll n = a.size();
vll used(n);
rep(v,n) if(!used[v]){
ll nv = v;
while(!used[nv]){
used[nv] = true;
nv = a[nv];
}
ret ^= 1;
}
return ret ^ (n&1);
}
bool solve(vll a, vll b){
{
vll na = a, nb = b;
sort(all(na));
sort(all(nb));
if(na != nb) return false;
}
{
vll na = a;
sort(all(na));
na.erase(unique(all(na)), na.end());
if(na.size() != a.size()) return true;
}
{
return f(a) == f(b);
}
}
int main() {
ll n;
cin >> n;
vll a(n); cinv(a); rep(i,n) a[i]--;
vll b(n); cinv(b); rep(i,n) b[i]--;
yesno(solve(a,b));
return 0;
}
