Burnside引理和Pólya定理

不想写很多冗杂的群论定义，所以本博客不是用来入门的。

概要

对于一个作用在集合 \(X\) 上的有限群 \(G\) ，对于每个 \(g\in G\) 令 \(X^g\) 表示 \(X\) 在 \(g\) 作用下的不动元素，即 \(X^g={x|x\cdot g=x,x\in X}\) ，则轨道数 \(|X/G|=\dfrac{\sum\limits_{g\in G}|X^g|}{|G|}\) 。
假设 \(X\) 中的两个元素 \(x_1,x_2\) ，存在变换，使得 \(x_1\cdot g=x_2\) ，则称 \(x_1\) 和 \(x_2\) 在同一个等价类里，上式中 \(|X/G|\) 就是等价类的数量。

好像也没有说明白，假设群 \(G\) 里面的 \(g\) 均表示图形的某种变换（如平移，旋转，翻折等），能够在进行一系列变换之后能够完全重合的图形成为同一种图形，对于某一种变换 \(g\) ，设有 \(c(g)\) 个图形属于某个图形的集合 \(X\) 在这种变换下和自己重合，则不同的图形一共有 \(\dfrac{1}{|G|}\sum\limits_{g\in G}c(g)\) 种。

举个例子：对于正三角形的三个顶点，我们用实心点和虚心点来标记，假设变换为旋转和翻折，则我们会有如下的6种变换方式。

对于所有可能存在的 \(2^3=8\) 个三角形，我们可以知道每一种变换分别有多少个三角形是不变的 \(c(g_1)=8,c(g_2)=2,c(g_3)=2,c(g_4)=4,c(g_5)=4,c(g_6)=4\) 。
所以本质不同的正三角形一共有 \(\dfrac{\sum\limits_{g\in G}c(g)}{|G|}=\dfrac{8+2+2+4+4+4}{6}=4\) 个，暴力验证一下就是这个答案。

接下来我们就可以考虑如下的问题了：我们对于一个图形（可能是网格，也可能是多面体，甚至可以是一个树或者图），要将它用 \(m\) 中颜色染色，置换群为 \(G\) ，问有多少种本质不同的方案。
我们考虑对于一个置换 \(g\in G\) 有哪些染色方案是不会变化的，也就是 \(c(g)\) 的值为多少。
不难发现，如果可以将置换表示成 \(k=\sigma(g)\) 环，只有每一个环内的所有颜色相同的时候，方案才不会变化，每个环有 \(m\) 种颜色可选，所以 \(c(g)=m^k\) 。
也就是说，本质不同的方案一共有 \(\dfrac{1}{|G|}\sum\limits_{g\in G}m^{\sigma(g)}\) ，这个也就是我们熟知的Pólya定理了。

例题

Luogu P4980 【模板】Pólya 定理

对于这个环，它的置换群就是 \(n\) 种旋转方式，假设某一个旋转是将所有的点对应向后的 \(k\) 第个，也就意味着他们会出现 \(\gcd(n,k)\) 个环，也就意味着有 \(n^{\gcd(n,k)}\) 种方案在这种变换下不会改变。
所以最终答案为 \(\dfrac{1}{n}\sum\limits_{i=1}^nn^{\gcd(n,i)}=\dfrac{1}{n}\sum\limits_{d|n}n^d\sum\limits_{i=1}^n[gcd(n,i)==d]=\dfrac{1}{n}\sum\limits_{d|n}n^d\sum\limits_{i=1}^{\frac{n}{d}}[gcd(\frac{n}{d},i)==1]=\dfrac{1}{n}\sum\limits_{d|n}\varphi(\frac{n}{d})n^d\) 。
暴力枚举 \(\leqslant \sqrt{n}\) 的因数，并暴力求解 \(\varphi(\frac{n}{d})\) 可以得到一个亚线性的做法。

[蓝桥杯 2015 国 B] 模型染色

置换群由满足在变换之后图同构的置换构成，对于这个顶点的置换，我们可以用 \(O(n)\) 的时间来求出环的数量。
由于 \(n\) 很小，暴力枚举所有的置换并判图是否同构即可。
最终复杂度为 \(O(m\times n!+n|G|)\) 。

[AHOI2002]黑白瓷砖

不难发现只有6种置换方式（具体可以参考最上面的例子）。
对于不变的置换（第一种），有 \(\dfrac{n(n+1)}{2}\) 个环。
对于旋转类置换（第二三种），有 \(\left\lceil\dfrac{n(n+1)}{6}\right\rceil\) 个环（除中心点外均三个一组）。
对于反转类置换（第四五六种），有 \(\dfrac{\frac{n(n+1)}{2}+\left\lceil\frac{n}{2}\right\rceil}{2}\) 个环（除对称轴上的均两两一组）。
所以最终答案为 \(\dfrac{2^{\frac{n(n+1)}{2}}+2\times 2^{\left\lceil\frac{n(n+1)}{6}\right\rceil}+3\times 2^{\frac{\frac{n(n+1)}{2}+\left\lceil\frac{n}{2}\right\rceil}{2}}}{6}\) ，需要写高精度。

[HNOI2009]图的同构计数

相当于对于完全图的每一条边染上黑色或者白色，问本质不同的方案数有多少。
置换群为所有 \(n!\) 种置换。
考虑对于一种置换有多少个环：
这 \(n!\) 种置换是和点编号的排列一一对应的，我们可以先找出这个排列中的所有环长 \(c_1,c_2\dots c_k\)。
对于两个不同的环 \(c_i,c_j\) 他们之间共有 \(c_ic_j\) 条边，这些边一共构成 \(\gcd(c_i,c_j)\) 个环。
对于某一个环 \(c_i\) ，其中一个节点向后跨越了 \(\leqslant \dfrac{c_i}{2}\) 个节点的边可以和所有环一一对应（对于 \(t> \dfrac{c_i}{2}\) 的，它和跨越 \(c_i-t\) 个节点的在同一个环内），也就是有 \(\left\lfloor\dfrac{c_1}{2}\right\rfloor\) 个环。
在所有的置换中一共有 \(\dfrac{n!}{\prod\limits_{i=1}^kc_i\cdot\prod\limits_{i-1}^n\sum\limits_{j=1}^k[c_j=i]}\) 个。
搜索 \(\{c\}\) 的值，对于每一种统计出答案即可。

[SHOI2006] 有色图

这题为上面一题的加强版，将 \(2\) 种颜色变为了 \(m\) 种颜色，方法和上面一题基本相同。