分类 算法 下的文章

Burnside 引理

ans = { 1 \over |G| } \sum_{f \in G} C(f) ,其中 C(f) 表示置换 f 中不动点的个数

Polya 定理

定义 L(f) 为置换 f 的循环节数,可以理解为对于任意一种状态至多经过 L(f) 次置换 f 可以变回原样。

易证置换 f 的不动点一定满足其自身的循环节为 L(f) ,即 C(f) = k^{L(f)} ,其中 k 表示颜色种数。

Polya 定理的公式即 ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)}

READ MORE