欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020牛客多校第三场-J Just Shuffle

程序员文章站 2022-08-15 19:55:15
题面:初始序列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#include#include#include#include

题面:初始序列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

相关标签: 基础算法