只要数量掌握置换群的概念这题就比较简单了: 对于一个排列A,给定一个置换P,置换 K 次后得到B(题目给你B和K让你求A)。 A ^ K = B 那么我们让B置换z次,使得z*K%r==0,(r为置换循环节)则会得到A。 证明: B ^ K = ,显然K*Z%r,形成循环,又回到自身A,即排列1,2,3,4…… 我们要求的置换P等于A再 置换一次。 那么我们令Z:Z * K % r == 1. 求出Z,然后让B置换Z次即可。显然Z就是K的逆元(百度逆元定义你就知道为什么了) 现在就差循环节了。 对于B来说,我们对每个环分开来处理,每个环的循环节即换的大小r。这样处理得到的依然时我们需要的结果。(即没必要求整体循环节(反正对于部分来说,其r|R,后面的置换不会改变))。 而这题保证了K是个大质数,则保证了K的逆元一定存在。。所以不会存在无解或者无法找到解的情况
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const double PI= acos(-1.0); const int M = 1e5+7; int vs[M],a[M],b[M]; vector<int>v; int n,k; void gao() { int r=v.size(),inv; for(int i=0;i<r;i++)if((ll)k*i%r==1)inv=i; for(int i=0;i<r;i++)b[v[i]]=v[(i+inv)%r]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i];// P ^ K = A //假设我们要求置换A ,z次 //A ^ z =P^(K*z) 其中 : K*z % r == 1 //因为置换取模r为0时刚好是 1 2 3 ……,需要再置换一次 //而K*z % r == 1 z=K^(-1),即K的逆元 for(int i=1;i<=n;i++) { if(!vs[i]) { v.clear(); int x=a[i]; while(!vs[x]) { vs[x]=1; v.pb(x); x=a[x]; } gao(); } } for(int i=1;i<=n;i++)printf("%d ",b[i]); puts(""); return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算