首页 > 代码库 > POJ 1721

POJ 1721

2024-07-27 12:23:58   218人阅读

好像不需要用到开方什么的。。。

可以知道，一副牌即是一个循环，那么，由于GCD(L,K)=1，所以一次洗牌后，亦是一个循环。其实，K次洗牌等于是T^(2^K)了。既然是循环，必定有周期。那么，周期是多少呢？以例子为例：1->4->6->2->7->3->5。其实对于第一个数（从零始）4，总会有先后移了2^a次方而回到原点，此时就是一个周期了。即是求2^a=1(mod n)。求出最小的a即可知道周期。s%a=t.那么，即是差a-t个状态就可以回到初始的了。

#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int num[1005];int tmp[1005];int ans[1005];int control(int n){	int ans=1;	for(int i=1;i<=n-1;i++){		ans=(ans*2)%(n);		if(ans==1)		return i;	}}int quick(int s,int n){	int res=1; int p=2;	while(s){		if(s&1) res=(res*p)%n;		s>>=1;		p=(p*p)%n;	}	return res;}int main(){	int n,s,cnt,k,pos;	while(scanf("%d%d",&n,&s)!=EOF){		for(int i=1;i<=n;i++)		scanf("%d",&num[i]);		int cy=control(n);	//	cout<<"cy="<<cy<<endl;		tmp[0]=1;		cnt=0; k=1;		while(num[k]!=1){			tmp[++cnt]=num[k];			k=num[k];		}	/*	for(int i=0;i<n;i++)		cout<<tmp[i]<<‘ ‘;		cout<<endl;*/		s=s%cy;		s=cy-s;	//	cout<<"s="<<s<<endl;		s=quick(s,n);	//	cout<<"s="<<s<<endl;		ans[0]=tmp[0];		pos=0;		for(int i=1;i<n;i++){			ans[i]=tmp[pos=(pos+s)%n];		}		for(int i=1;i<=n;i++){			num[ans[i-1]]=ans[i%n];		}		for(int i=1;i<=n;i++){			printf("%d\n",num[i]);		}	}	return 0;}

　　

POJ 1721


联系
我们