正文
POJ 2409 Let it Bead (Polya定理)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
题意
用k种颜色对n个珠子构成的环上色,旋转翻转后相同的只算一种,求不等价的着色方案数。
思路
Polya定理
X是对象集合{1, 2, ……, n}, 设G是X上的置换群,用M种颜色染N种对象,则不同的染色方案数为:
λ(g)表示置换g的轮换个数,且λ(g) = λ1(g) + λn(g) + …… + λn(g),其中λi(g)表示g中长度为i的轮换(循环)个数.
本题是对一个n个珠子的圆珠的颜色,而圆珠的置换群有:
Ⅰ翻转:1.当n为奇数时,有n种翻转,每种翻转的轴都是一个顶点和该顶点对边中点的连线,有n种置换,每种置换的轮换个数均为(n/2+1)。
2.当n为偶数时,有n种翻转,其中n/2种转轴是两个对应顶点连线,轮换个数为n/2+1;另n/2种转轴是两条对边中点的连线,轮换个数为n/2。
Ⅱ旋转:枚举旋转角度360/n*i,有n种旋转;第i种旋转有gcd(n, i)个轮换,每个轮换的长度都是n/gcd(n, i)。
然后带入公式即可.
代码
[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#define MID(x,y) ((x+y)/2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define REP(i, begin, end) for (int i = begin; i <= end; i ++)
using namespace std;
int gcd(int a, int b){
return b?gcd(b, a%b):a;
}
int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int c, s;
while(scanf("%d %d", &c, &s) != EOF){
long long res = 0;
if (c + s == 0) break;
if (s % 2 == 1){
res += (long long)s * pow(c, s/2+1);
}
else{
res += (long long)(s/2) * (pow(c, s/2) + pow(c, s/2+1));
}
for (int i = 1; i <= s; i ++){
res += (long long)pow(c, gcd(s, i));
}
printf("%I64d\n", res/2/s);
}
return 0;
}
[/cpp]