概念

  • 置换(permutation): 是将相异物件或符号根据确定的顺序重排。
  • 不动点: 对于一个置换$f$,若一个着色方案$s$经过置换后不变,称$s$为$f$的不动点
  • Burnside引理: 设$F$是一个$N = {1,2,…,n}$上的置换群,对于$F$中的一个置换$f$,其不动点数目记为$C(f)$,则等价类数目为$\frac{\sum C(f)}{|F|}$,即$C(f)$的平均值
  • polya定理: 对于一种置换,可以分解成$m(f)$个置换的乘积,每种循环内元素的颜色必须相同,若涂k种颜色,则有$C(f) = k^{m(f)}$,因此用k种颜色给n个元素着色。等价类数目为$\frac{\sum k^{m(f)}}{|F|}$

题目

HDU5868

n 个点的一个环,每个点可以染成黑色或白色,相邻两点不能是黑色,求旋转同构意义下的染色数

先不考虑同构,设$f(n)$为$n$个点染色的方案数,$f(n) = f(n-1) + f(n-2)$
根据 Burnside引理 $F(n) = \frac{1}{n}\sum_{i=1}^n f(gcd(i,n))$
即$F(n) = \frac{1}{n} \sum_{d|n} f(d)\phi(n/d)$
注意特判$n = 1$的情况

复杂度 $O(\sqrt{n}logn)$

uva10294

长度为n的项链,染t种颜色
分别求旋转意义下同构,和旋转翻转意义下同构的方案数

不动点个数
$a = \sum_{i=0}^{n-1} t^{gcd(i,n)}$
根据polya定理,旋转意义下,答案为$a/n$

翻转意义下
当$n$为奇数时,有n条对称轴
每条对称轴形成2个长度为2,1个长度为1的循环,即$(n+1)/2$个循环
不动点总数为$b = nt^{(n+1)/2}$

当$n$为偶数时,
有$n/2$条穿过珠子的对称轴,分别形成$n/2-1$长度为2的循环和两个长度为1的循环
$n/2$条不穿过珠子的对称轴,分别形成$n/2$个长度为2的循环
不动点总数为$b = n/2(t^{n/2+1} + t^{n/2})$

最后答案分别为$a/n$,$(a+b)/2n$

参考