burnside引理

前言

今天大概学习了一下burnside引理，下面来小结一下。

参考资料

南京外国语学校 陈瑜希 的集训队论文 polya计数法的应用

基本概念

（由于作者懒，直接截图）

置换群

顾名思义，就是一个元素都是置换的群。对于置换群，它的二元运算就是置换之间的连接，比如说

含义就是先经过第一个置换，在经过第二个置换，等价于经过第三个置换。

burnside引理

|G|$|G|$表示置换群的大小。
看不懂没关系，我们先看一道例题。

例题

SGU294 He’s Circles

题意：有一个长度为N$N$的环，上面写着’X’和’E’，问本质不同的环有多少种。(N<=200000)$(N<=200000)$。
分析：这就是一道运用burnside引理的裸题。在本题中，共有N$N$种置换，分别表示环转1$1$个位置、2$2$个位置……N$N$个位置，那么现在对于每种置换，我们需要求出有多少种情况经过这种置换后依然保持不变。那么如何求解呢？假设N=8$N=8$，转了2$2$个位置，那么每个位置的变化情况是：1−>3−>5−>7−>1,2−>4−>6−>8−>2$1->3->5->7->1,2->4->6->8->2$，x−>y$x->y$表示原来x$x$位置上的到了y$y$位置，我把这样的一个东西叫做循环节。因为我们求的是不变的情况，所以同一个循环节中的位置上的字母应该是一样的，那么我们只需要知道循环节的个数K$K$，就可以知道对于这种置换不变的方案数为2K$2^K$，有一个比较显然的结论，当转了i$i$个位置时循环节的个数即为gcd(i,N)$gcd(i,N)$，所以，本题的答案即为∑ni=12gcd(i,N)N$\frac{\sum _{i=1}^n{2}^{gcd(i,N)}}{N}$。
先写这么多。完结撒花！