POJ 2409 Let it Bead

算是我第一道理解的burnside引理题目

题意

c 种颜色的珠子,组成长为 s 的项链,通过旋转或者翻转得到的情况我们算一种,问总共有多少种不同的方案。

 

思路

Polya定理的应用

设 G 是 p 个对象的一个置换群,用 k 种颜色去染这 p 个对象,若一种染色方案在群 G 的作用下变成另一种方案,则这两个方案当作是同一种方案,这样的不同染色方案数为:

L=1/|G|∗∑(k^C(f)),f∈G

其中, C(f) 为循环节, |G| 表示群的置换方法数。

对于有 n 个位置的项链,有 n 种旋转置换和 n 种翻转置换

对于旋转置换:

C(fi)=gcd(n,i) , i 表示一次转过 i 颗珠子, i=0 时 C(f0)=n

对于翻转置换:

  • 如果 n 为偶数:则有 n/2 个置换 C(f)=n/2 (以两条对边中点为轴翻转) ,还有 n/2 个置换 C(f)=n/2+1 (以两个对点为轴翻转)
  • 如果 n 为奇数: C(f)=n/2+1 (以一个点和其对边中点为轴翻转)

 

9 + 5 =