Plóya定理

Plóya定理一般用于求着色在翻转/旋转后的不同方案数，很多书上都有介绍。

poj 2409 Let it Bead

http://poj.org/problem?id=2409

题目的大概意思是：给出c种颜色和s个珠子，让你来染色，求经翻转和旋转后最后能得到的不同染色方案数。

这就一个非常基本的Plóya问题。

#include<stdio.h>
#include<math.h>
int gcd(int a, int b) {
	if(!b)
		return a;
	else
		return gcd(b, a%b);
}
int main() {
//freopen("in.txt", "r", stdin);
	int c, s;
	__int64 ans;
	while(scanf("%d%d", &c, &s) && (c | s)) {
		ans = 0;
		//旋转
		for(int i=1; i<=s; i++)
			ans += __int64(pow((double)c, (double)gcd(s, i)));
		//翻转
		if(s & 1) {
			ans += (__int64)(pow((double)c, (s+1.0)/2) * s);
		} else {
			ans += (__int64)(pow((double)c, s/2.0) * s / 2);
			ans += (__int64)(pow((double)c, (s+2.0)/2) * s / 2);
		}
		ans /= (s<<1);
		printf("%I64d/n", ans);
	}
	return 0;
}

poj 1286Necklace of Beads

http://poj.org/problem?id=1286

这题与2409基本一样，只是在这题种颜色数是固定的3种(red, blue or green)，输入n表示珠子个数。

注意：要特别处理n==0，应该输出0，为此贡献了两个RE，囧。

#include<stdio.h>
#include<math.h>
int gcd(int a, int b) {
	if(!b)
		return a;
	else
		return gcd(b, a%b);
}
int main() {
//freopen("in.txt", "r", stdin);
	int c = 3, s;
	__int64 ans;
	while(scanf("%d", &s) && s != -1) {
		if(s == 0) {
			puts("0");
			continue;
		}
		ans = 0;
		//旋转
		for(int i=1; i<=s; i++)
			ans += __int64(pow((double)c, (double)gcd(s, i)));
		//翻转
		if(s & 1) {
			ans += (__int64)(pow((double)c, (s+1.0)/2) * s);
		} else {
			ans += (__int64)(pow((double)c, s/2.0) * s / 2);
			ans += (__int64)(pow((double)c, (s+2.0)/2) * s / 2);
		}
		ans /= (s<<1);
		printf("%I64d/n", ans);
	}
	return 0;
}