链接
https://ac.nowcoder.com/acm/contest/5667/J
题意
求序列 ${1,2,3,…,n}$ 按照 $P$ 置换 $k$（$10^8\le k\le 10^9$，$k$ 为质数） 次后为 $A$，已知 $k$ 和 $A$，求按照 $P$ 置换一次后的序列
思路
设原序列为 $E$，$E*P^k=P^k=A$
找出所有循环置换，对于某个循环置换，设 $sz$ 为环的大小，$U$ 为 $P$ 的子序列，$V$ 为 $A$ 的子序列，那么 $U^{k%sz}=V$，$V^{k^{-1}%sz}=U$
因为 $\gcd(k,sz)=1$，又因为模数较小，所以对于 $kx%sz=1$ 可以枚举 $x$ 求出逆元
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,p[N],cnt,vis[N],res[N];
int m;
vector<int> v[N];
void find_cycle(int x) {
if(vis[x]) return;
vis[x]=cnt;
v[cnt].push_back(x);
find_cycle(p[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) {
if(vis[i]) continue;
++cnt;
find_cycle(i);
int sz=v[cnt].size(),inv;
for(int j=0;j<sz;j++) if(1ll*m*j%sz==1) {inv=j;break;}
for(int j=0;j<sz;j++) res[v[cnt][j]]=v[cnt][(j+inv)%sz];
}
for(int i=1;i<=n;i++) printf("%d ",res[i]);
puts("");
return 0;
}
|