题目链接

分析： 题意：已知K次置换后的序列，求初始置换

因为是反向求置换，所以求出置换的循环节X后，需要旋转 X−K(mod)X X − K ( m o d ) X 次 模拟了一下样例，跑不出答案怎么回事啊？？

实际上样例的循环节是3：

6 3 1 2 4 7 5 first change: 7 1 6 3 2 5 4

ans[i]=a[a[i]] a n s [ i ] = a [ a [ i ] ]

6 3 1 2 4 7 5 first change: 7 1 6 3 2 5 4 second change: 4 7 5 6 1 2 3 third change: 6 3 1 2 4 7 5

实际上这种置换不是一个置换若干乘积 而是每次都已当前序列为新的置换

因此我们只能暴力模拟，找到整个序列的循环节

tip

样例都是骗人的 题目给出的样例在自乘4次之后就可以变换成答案。。。一开始被迷惑了

#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=1002; int a[N],m,n,belong[N],cnt[N],A[N],B[N]; int pd() { for (int i=1;i<=n;i++) if (a[i]!=A[i]) return 0; return 1; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]),A[i]=a[i]; int tt=0; do { tt++; for (int i=1;i<=n;i++) B[i]=A[A[i]]; memcpy(A,B,sizeof(A)); } while(!pd()); tt=tt-m%tt; memcpy(A,a,sizeof(A)); for (int i=1;i<=tt;i++) { for (int i=1;i<=n;i++) B[i]=A[A[i]]; memcpy(A,B,sizeof(A)); } for (int i=1;i<=n;i++) printf("%d\n",A[i]); return 0; }