1286 polya.cpp

各种算法

#include"iostream"
using namespace std;
#include"map"
#include"math.h"
#include <algorithm>
#define N 100
#define M 2*N
int a[N];
int rep[M];//各置换循环节数
void rotate(int n)//旋转的循环节总数
{	int b[N];int i,j;
	for( i = 0;i < n; i++)	a[i] = i;
	for(	i = 1;i <= n-1; i++)
	{	int t = a[0];
		for( j = 0;j < n-1; j++) a[j] = a[j+1];
		a[n-1] = t;		//设置置换类
		memset(b,0,sizeof b);
		int knob = 0;
		for( j = 0;j < n; j++){
			if(b[j]) continue;
			for(int k = a[j]; k != j; k = a[k]) {b[k] = 1;}
			knob++;
		}
		rep[i] = knob;
	}
}
void symmetry(int n)//对称轴翻转
{	int i,j;
	if(n%2) for( i = n; i< 2*n; i++) rep[i] = (n+1)/2;
	else {
		for( i = n;i < n+n/2; i++) rep[i] = (n+2)/2;
		for( j = i;j < i+n/2; j++) rep[j] = n/2;
	}
}
__int64 polya(int n,int m)
{	int g = 2*n;
	__int64 p = 0;
	for(int i = 0;i < g; i++) {
		p += (__int64)pow((double)m,rep[i]);
	}
	return p/g;
}
int main()
{	int n,m = 3;
	while(scanf("%d",&n),n != -1) {
		if(n <= 0) {cout<<0<<endl;continue;}
		rep[0] = n;
		rotate(n);
		symmetry(n);
		printf("%lld\n",polya(n,m));
	}
	return 1;
}

//用c++交
//POlyA原理