2020牛客暑期多校训练营（第二场） J Just Shufflebjfu170203101的博客-j just shuffle

只要数量掌握置换群的概念这题就比较简单了：

对于一个排列A，给定一个置换P,置换 K 次后得到B（题目给你B和K让你求A）。

A ^ K = B

那么我们让B置换z次，使得z*K%r==0，(r为置换循环节)则会得到A。

证明：

B ^ K =  ，显然K*Z%r，形成循环，又回到自身A，即排列1，2，3，4……

我们要求的置换P等于A再 置换一次。

那么我们令Z：Z * K % r == 1.

求出Z，然后让B置换Z次即可。显然Z就是K的逆元（百度逆元定义你就知道为什么了）

现在就差循环节了。

对于B来说，我们对每个环分开来处理，每个环的循环节即换的大小r。这样处理得到的依然时我们需要的结果。（即没必要求整体循环节（反正对于部分来说，其r|R，后面的置换不会改变））。

而这题保证了K是个大质数，则保证了K的逆元一定存在。。所以不会存在无解或者无法找到解的情况

 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const double PI= acos(-1.0); const int M = 1e5+7;  int vs[M],a[M],b[M]; vector<int>v; int n,k; void gao() {  int r=v.size(),inv;  for(int i=0;i<r;i++)if((ll)k*i%r==1)inv=i;  for(int i=0;i<r;i++)b[v[i]]=v[(i+inv)%r]; } int main() {  ios::sync_with_stdio(false);    cin.tie(0);  cin>>n>>k;  for(int i=1;i<=n;i++)cin>>a[i];// P ^ K = A   //假设我们要求置换A ，z次   //A ^ z =P^(K*z)  其中 ： K*z % r == 1 //因为置换取模r为0时刚好是 1 2 3 ……，需要再置换一次  //而K*z % r == 1  z=K^(-1),即K的逆元    for(int i=1;i<=n;i++)  {   if(!vs[i])   {    v.clear();    int x=a[i];    while(!vs[x])    {     vs[x]=1;     v.pb(x);     x=a[x];    }    gao();   }  }   for(int i=1;i<=n;i++)printf("%d ",b[i]);  puts("");  return 0; }