2020 牛客多校暑期第二场
程序员文章站
2022-05-14 08:09:57
...
ps:用来监督自己补题
J.Just Shuffle
题意:
初始是1 2…n,给你一个置换函数 f^k之后得到的数列,问 f 是什么,继续背锅…一开始我记得我的置换定义是没有错的,但是自己傻叉了手推样例的时候推不对,以为自己错了,结果听老板搞了个错的题意,居然还可以推出来样例,后面自闭3h推不出,一开始我就往同余想了,结果自己sb手写样例还算错,无语了
思路:
首先得搞懂置换是什么东西,其实可以看成是一一映射,举例来说,如下图。
知道置换是什么东西就好搞了,事实上,对于一个置换,我们会产生一些环,也就是经过一段周期后回到初始位置,我们设答案 F这个函数形成的环的 size分别为 sz1,sz2…我们发现,其实我们已知F走k到达的点,现在求每个点走第一步到达的点,由于k是个大质数,所以有以下做法
简单来说就是在F^k上走inv(k,size (F ^k))步走到的地方就等于答案,所以根据输入构造下环求个逆元就秒了
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn],ans[maxn],x,y;
bool v[maxn];
int exgcd(int a,int b,int &x,int &y){
if(!b){ x=1,y=0;return a;}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
int inv(int k,int size){
exgcd(k,size,x,y);
return (x%size+size)%size;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
if(v[i])continue;
vector<int>tmp;
tmp.pb(i);v[i]=1;
int now=a[i];
while(now!=i){
tmp.pb(now);v[now]=1;
now=a[now];
}
int sz=tmp.size();
int ni=inv(k,sz);
for(int i=0;i<sz;++i)
ans[tmp[i]]=tmp[(i+ni)%sz];
}
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}
上一篇: 第一届祥云杯密码学(一)
下一篇: 2020牛客第二场
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
牛客多校第三场 A-Clam and Fish【贪心】+ B-Classical String Problem【思维】
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客多校第三场-J Just Shuffle
-
【杭电多校2020】第二场1001.Total Eclipse(并查集)
-
2020牛客多校第3场[Clam and Fish+贪心]