题面:初始序列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
如对本文有疑问, 点击进行留言回复!!
CodeForces 1393C Pinkie Pie Eats Patty-cakes
Codeforces Round #662 (Div. 2) A - Rainbow Dash, Fluttershy and Chess Coloring
网友评论