记录编号	84788	评测结果	AAAAAAAAAA
题目名称	[CEOI 1998]洗牌机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2013-12-19 21:21:15	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
const int SIZEN=1001;
int N,S;
class REPLACE{
public:
	int a[SIZEN];
	void output(void){
		for(int i=1;i<=N;i++) cout<<a[i]<<" ";cout<<endl;
	}
	REPLACE(){//初始化为单位置换
		int i;
		for(i=1;i<=N;i++) a[i]=i;
	}
	void inverse(void);
};
void REPLACE::inverse(void){
	int at[SIZEN]={0};
	int i;
	for(i=1;i<=N;i++) at[i]=a[i];
	for(i=1;i<=N;i++) a[at[i]]=i;
}
int* getcyc(REPLACE &x){//将x表示为循环形式(确保为单循环)
	int *ans=new int[SIZEN];
	int i,k,tot=1;
	bool flag[SIZEN]={0};
	for(i=1;i<=N;i++){
		if(!flag[i]){
			k=i;
			do{
				flag[k]=true;
				ans[tot++]=k;
				k=x.a[k];
			}while(k!=i);
		}
	}
	return ans;
}
int modN(int x){
	return ((x%N)+N)%N;
}
REPLACE* pow(REPLACE &x,int n){//将置换x作n次方,返回'新置换'这一对象的位置
	REPLACE *ans_key=new REPLACE;
	REPLACE &ans=(*ans_key);
	int *cyc=getcyc(x);
	int atp[SIZEN]={0,1};
	int i=1,j=1,now=1,next;
	//x的循环每次向后走1个,atp每次向后走k个
	do{
		atp[j]=cyc[i];
		i--;i=modN(i-1)+1;
		j-=n;j=modN(j-1)+1;
	}while(i!=1);
	for(i=1;i<N;i++) ans.a[atp[i]]=atp[i+1];
	ans.a[atp[N]]=atp[1];
	return ans_key;
}
REPLACE P;
int quickpow(int a,int n){//a^n mod N
	int ans=1;
	while(n){
		if(n&1) ans=(ans*a)%N;
		a=(a*a)%N;
		n>>=1;
	}
	return (ans+N)%N;
}
bool init(void){
	if(scanf("%d%d",&N,&S)==EOF) return false;
	for(int i=1;i<=N;i++) scanf("%d",&P.a[i]);
	return true;
}
void work(void){
	int *s=getcyc(P);
	REPLACE &ans=(*pow(P,quickpow(2,S)));
	for(int i=1;i<=N;i++) printf("%d\n",ans.a[i]);
}
int main(){
	freopen("shuffle.in","r",stdin);
	freopen("shuffle.out","w",stdout);
	init();
	work();
	return 0;
}