https://ac.nowcoder.com/acm/contest/5667/J

題目大意：給你一個置換A，使得置換P^k=A,讓你求出置換P。

思路：我們根據置換A再置換z次，那么就等于置換p 置換z*k次,如果z*k%len==0，那么將會回到單位序列，那我們再置換一次則是置換p，即是z*k%len==1，則z是k在模len下的逆元。我們求出A的每一個循環，再求出z，就可以求出該循環內的對應位置。因為滿足gcd（len，k）==1,那我們可以直接在循環中將i后移z個位置。

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define pb push_back #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=998244353; const ll N =5e5+10; const ll M =250000; const double eps = 1e-4; //const double pi=acos(-1); ll re(){ll x;scanf("%lld",&x);return x; } ll n,k; int a[N]; int vis[N]; int b[N]; vector<int> g; void gg(){ll l=g.size(),p=0;for(ll i=0;i<l;i++) if((i*k)%l==1) {p=i;break;}for(ll i=0;i<l;i++) b[g[i]]=g[(i+p)%l]; } void slove(){n=re(),k=re();for(int i=1;i<=n;i++) a[i]=re();for(int i=1;i<=n;i++){if(vis[i]) continue;int x=i;g.clear();while(!vis[x]){vis[x]=1;g.pb(x);x=a[x];}gg();}for(int i=1;i<=n;i++) printf("%d ",b[i]); } int main(){int t=1;// t=re();while(t--) slove();return 0; }

總結

以上是生活随笔為你收集整理的2020牛客暑期多校训练营（第二场）Just Shuffle的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。