置换(polya).txt

浙大ACM编程竞赛的摸板(内部质料),吐血奉献!!!!里面内容超多,把ACM题目分成了好几类,没一个类型都有详细的代码

//求置换的循环节,polya原理
//perm[0..n-1]为0..n-1的一个置换(排列)
//返回置换最小周期,num返回循环节个数
#define MAXN 1000

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int polya(int* perm,int n,int& num){
	int i,j,p,v[MAXN]={0},ret=1;
	for (num=i=0;i<n;i++)
		if (!v[i]){
			for (num++,j=0,p=i;!v[p=perm[p]];j++)
				v[p]=1;
			ret*=j/gcd(ret,j);
		}
	return ret;
}