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

2020 牛客多校暑期第二场

程序员文章站 2022-05-14 08:09:57
...

ps:用来监督自己补题
J.Just Shuffle
题意:
初始是1 2…n,给你一个置换函数 f^k之后得到的数列,问 f 是什么,继续背锅…一开始我记得我的置换定义是没有错的,但是自己傻叉了手推样例的时候推不对,以为自己错了,结果听老板搞了个错的题意,居然还可以推出来样例,后面自闭3h推不出,一开始我就往同余想了,结果自己sb手写样例还算错,无语了

思路:
首先得搞懂置换是什么东西,其实可以看成是一一映射,举例来说,如下图。
2020 牛客多校暑期第二场
知道置换是什么东西就好搞了,事实上,对于一个置换,我们会产生一些环,也就是经过一段周期后回到初始位置,我们设答案 F这个函数形成的环的 size分别为 sz1,sz2…我们发现,其实我们已知F走k到达的点,现在求每个点走第一步到达的点,由于k是个大质数,所以有以下做法
2020 牛客多校暑期第二场
简单来说就是在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; 
}
相关标签: 牛客多校