2020牛客暑期多校训练营（第二场） J Just Shuffle

初始序列1,2,3,4,5…设为a,有一个置换p，a置换k次后成了b；
题目给了b，k，求a置换一次的结果；
对于b可以求出一些循环节，长度设为r，设一个数z，使得zk%r==1；即a转zk次后为1；即是答案；
z可以用逆元也可以直接试，不超过r；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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 do()
{
	int r=v.size(),z;
	for(int i=0;i<r;i++)
		if((ll)k*i%r==1)z=i;
	for(int i=0;i<r;i++)
		b[v[i]]=v[(i+z)%r];
}
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];

	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];
			}
			do();
		}
	} 
	for(int i=1;i<=n;i++)printf("%d ",b[i]);
	puts("");
	return 0;
}