题解 P2227 【[HNOI2001]洗牌机】

题目链接

Solution [HNOI2001]洗牌机

题目大意：给定一个长为(n)的只有一个轮换的置换，告诉你平方(s)次之后的结果，求原置换

置换开方

---

详见《潘震皓：置换群快速幂运算研究与探讨》（2005年国集论文）

关键在于如果一个长为(n)的置换(T)只有一个轮换，那么(T^n=I)，I为单位置换

所以(sqrt{T}=sqrt{T^{n+1}}=T^{frac{n+1}{2}})

快速幂即可，复杂度(O(snlogn))

#include <cstdio>
using namespace std;
const int maxn = 1024;
int n,s;
struct Node{
	int val[maxn];
	Node operator * (const Node &rhs)const{
		Node res;
		for(int i = 1;i <= n;i++)
			res.val[i] = rhs.val[val[i]];
		return res;
	}
}now;
inline Node qpow(Node a,int b){
	Node res,base = a;
	for(int i = 1;i <= n;i++)res.val[i] = i;
	while(b){
		if(b & 1)res = res * base;
		base = base * base;
		b >>= 1;
	}
	return res;
}
int main(){
	scanf("%d %d",&n,&s);
	for(int i = 1;i <= n;i++)scanf("%d",now.val + i);
	for(int i = 1;i <= s;i++)now = qpow(now,(n + 1) >> 1);
	for(int i = 1;i <= n;i++)
		printf("%d%c",now.val[i]," 
"[i == n]);
	return 0;
}