2020 牛客多校暑期第二场

ps:用来监督自己补题
J.Just Shuffle
题意：
初始是1 2…n，给你一个置换函数 f^k之后得到的数列，问 f 是什么，继续背锅…一开始我记得我的置换定义是没有错的，但是自己傻叉了手推样例的时候推不对，以为自己错了，结果听老板搞了个错的题意，居然还可以推出来样例，后面自闭3h推不出，一开始我就往同余想了，结果自己sb手写样例还算错，无语了

思路：
首先得搞懂置换是什么东西，其实可以看成是一一映射，举例来说，如下图。

知道置换是什么东西就好搞了，事实上，对于一个置换，我们会产生一些环，也就是经过一段周期后回到初始位置，我们设答案 F这个函数形成的环的 size分别为 sz1,sz2…我们发现，其实我们已知F走k到达的点，现在求每个点走第一步到达的点，由于k是个大质数，所以有以下做法

简单来说就是在F^k上走inv(k,size (F ^k))步走到的地方就等于答案，所以根据输入构造下环求个逆元就秒了

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn],ans[maxn],x,y;
bool v[maxn];
int exgcd(int a,int b,int &x,int &y){
   if(!b){ x=1,y=0;return a;}
   int d=exgcd(b,a%b,x,y);
   int z=x;x=y;y=z-y*(a/b);
   return d; 
}
int inv(int k,int size){
    exgcd(k,size,x,y);
    return (x%size+size)%size;
}
int main()
{ 
   int n,k;
   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;++i)
      scanf("%d",&a[i]);
   for(int i=1;i<=n;++i){
      if(v[i])continue;
      vector<int>tmp;
      tmp.pb(i);v[i]=1;
      int now=a[i];
      while(now!=i){ 
          tmp.pb(now);v[now]=1;
          now=a[now];  
      } 
      int sz=tmp.size();
      int ni=inv(k,sz);
      for(int i=0;i<sz;++i)
         ans[tmp[i]]=tmp[(i+ni)%sz]; 
   } 
   for(int i=1;i<=n;++i)
       printf("%d ",ans[i]);
   return 0; 
}