置换

给定长度为 $n$ 的置换 $A$ 和 $B$ ，问是否存在一个正整数 $k$ ，使得 $A^k=B$ 。

置换可以被理解为一个 $[1,n] \cap \mathbb{Z}$ 到 $[1,n] \cap \mathbb{Z}$ 的双射 $F$ ， $F_i$ 表示数字 $i$ 经过该映射变换后的数字。置换的 $k$ 次幂被定义为映射的 $k$ 次复合。

例： $A = [1,3,2,5,4]$ 是一个长度为 $5$ 的置换， $A^2 = [1,2,3,4,5]$ ，即 $A(A(1)) = A(1) = 1 , A(A(2)) = A(3) = 2 , A(A(3)) = A(2) = 3 , A(A(4)) = A(5) = 4 , A(A(5)) = A(4) = 5$

注：本题并不要求计算出 $k$ 的值，只是判断 $k$ 的存在性。

第一行一个数 $T$ 表示数据组数。

接下来有 $T$ 组数据，每组数据：
第一行一个正整数数 $n$ ，接下来一行 $n$ 个正整数表示 $A$ ，接下来一行 $n$ 个正整数表示 $B$ 。
保证给出的都是合法的置换。
$1\leq T\leq 10 , 1\leq n \leq 10^5$

#include<bits/stdc++.h> using namespace std; int s[1000050]; int ss[1000050]; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>s[i]; } for(int i=1;i<=n;i++){ cin>>ss[i]; } int f=0; for(int i=1;i<=n;i++){ if(s[s[i]]==i&&s[s[i]]!=ss[i]){ f=1; break; } } cout<<(f?"No":"Yes")<<endl; } return 0; }

详情