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>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1),eps=1e-8;
const int maxn=1e5+10;
int n,k;
int a[maxn],b[maxn]; 
bool vis[maxn];
vector<int>num;
void f(){
	int len=num.size(),z;
	for(int i=0;i<len;i++){
		if((ll)k*i%len==1)z=i;
	}
	for(int i=0;i<len;i++)
		b[num[i]]=num[(i+z)%len];
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		vis[i]=0;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			num.clear();
			int tmp=i;
			while(!vis[tmp]){
				vis[tmp]=1;
				num.push_back(tmp);
				tmp=a[tmp];
			}
			f();
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",b[i]);
	puts("");
 	return 0;
}




/**
 *　　　　　　　　┏┓　　 　┏┓
 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　　　┃　　　　　　　┃ 　
 * 　　　　　　　┃　　　━　　 　┃
 * 　　　　　　　┃　＞　　　＜　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃...　⌒　... 　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃  　　　　　　
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┗━━━┓
 * 　　　　　　　　　┃　　　　　　　┣┓
 * 　　　　　　　　　┃　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛
*/

本文地址：https://blog.csdn.net/qq_43624815/article/details/107567910