题解 P2227 【[HNOI2001]洗牌机】

· · 题解

《潘震皓：置换群快速幂运算研究与探讨》（2005年国集论文）里面有详细说这题。本质上上一个置换开方问题，每洗牌一次，相当于把置换平方以下，总共2^s次，所以逆运算就是把置换p1..pn开2^s次方

由于n是奇数，gcd(2^s,n)=1，并且根据题意，这个置换是一个轮换（只有一个循环节），根据论文所属，在此情况下置换开方有唯一解，并且可以在O(n)搞定。大致思路如下：

1.将p写成轮换形式，设为a1..an 2.倒推k=2^s次方根的轮换b1..bn，根据论文，有b[1+(i-1)*k]=a[i]（下标都在模n的意义下） 3.由b再倒推出置换x

关键的第二步，原文有图，洛谷传图实在是不方便。。自己去找原文吧。。

附代码

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,s,x[N],p[N],A[N],B[N],z=1;
int main(){
    scanf("%d%d",&n,&s);
    for (int i=1;i<=n;i++) scanf("%d",&p[i]);
    for (int i=1,j=1;i<=n;i++,j=p[j]) A[i]=p[j];
    for (int i=1;i<=s;i++) z=(z*2)%n;
    for (int i=1,j=1;i<=n;i++,j=(j+z-1)%n+1) B[j]=A[i];
    for (int i=1;i<=n;i++) x[B[i]]=B[i%n+1];
    for (int i=1;i<=n;i++) cout<<x[i]<<" ";
    return 0;
}