牛客contest5667-J

传送门

题目大意

给一个长度为n的序列A={1,2,3,…,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。 输入n,k和B，输出A，如果无解则输出-1。

思路

这种“给出原序列、目标序列与置换规则”的题一般都是置换群。

首先给你一个序列，假如：
s = {1 2 3 4 5 6}
然后给你一个变换规则
t = {6 3 4 2 1 5}
就是每一次按照t规则变换下去
比如这样
第一次：6 3 4 2 1 5
第二次：5 4 2 3 6 1
第三次：1 2 3 4 5 6
发现经过几次会变换回去，在变换下去就是循环的了，这就是一个置换群。

CSDN博主 Yoangh

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; 

const int LIM = 1e5+10;

ll n, k;
ll arr[LIM], ans[LIM];
bool check[LIM];

vector<ll>v;

void dataDeal()
{
	ll m = v.size(), tmp;
	
	for ( ll i = 0; i < m; i++ )
		if ( (k * i) % m )
			tmp = i;
			
	for ( ll i = 0; i < m; i++ )
		ans[v[i]] = v[(i + tmp) % m];
}


int main()
{
	scanf( "%lld%lld", &n, &k );
	for ( ll i = 1; i <= n; i++ )
		scanf( "%lld", &arr[i] );
	
	ll x;
	for ( ll i = 1; i <= n; i++ )
	{
		if ( check[i] ) continue;
		
		v.clear();
		x = arr[i];
		
		while ( !check[x] )
		{
			v.push_back( x );
			check[x] = 1;
			x = arr[x];
		}
		
		dataDeal();
	}
	
	for ( ll i = 1; i <= n; i++ )
		printf( "%lld ", ans[i] );
	
	return 0;
}