polya定理

这是组合数学中著名的定理。用于解决“本质不同的染色方案”计数问题。

问题

现在需要给$2\times 2$的棋盘黑白染色。求本质不同的染色方案数。

如果某染色方案经过顺时针旋转后与别的染色方案相同，则称它们本质相同。

暴力

我们先暴力列出每种染色方案： 

发现本质不同的染色方案数有$6$种：C1,C2,C6,C10,C12,C16。

burnside引理

burnside引理是polya定理的基础。

为了讨论方便，先给格子编号。

首先考虑“旋转”的本质——置换。旋转给出了一些置换方式，例如顺时针旋转${90}^{\circ }$，用置换的语言说就是“原来的位置是1的现在摆在2，原来位置是2的现在摆在3……”，表示为$\{2,3,4,1\}$。类似地，我们搞出所有的置换：

$f_{0^{\circ }}=\{1,2,3,4\}$
$f_{{90}^{\circ }}=\{2,3,4,1\}$
$f_{{180}^{\circ }}=\{3,4,1,2\}$
$f_{{270}^{\circ }}=\{4,1,2,3\}$

接下来就是burnside引理了：

对于每个置换$f$，我们定义$C\left(f\right)$为在置换 $f$ 下保持不变的方案数。
则有： 本质不同的方案数为$C\left(f\right)$的平均数。
即：$\text{ans}=\frac{1}{|G|}\sum _{f\in G}C\left(f\right)$

用上面的例子来验证一下：

置换$f$	保持不变的方案	$C\left(f\right)$
$0^{\circ }$	1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16	16
${90}^{\circ }$	1,16	2
${180}^{\circ }$	1,10,11,16	4
${270}^{\circ }$	1,16	2

则$C\left(f\right)$的平均数为：$\frac{16+2+4+2}{4}=6$，发现确实是答案。

polya定理

上面的burnside引理很好用，然而它需要枚举每个方案，复杂度十分不好。

所以polya定理出来拯救世界了。它提供了一种快速计算$C\left(f\right)$的方法：

考虑置换$f$，我们一定能把它表示成循环的形式。例如上面的转${180}^{\circ }$可以表示为：$\{3,4,1,2\}=(1,3)(2,4)$。

令$m\left(f\right)$表示置换$f$的循环节个数，$k$表示有多少种颜色。则有：

$C\left(f\right)=k^{m\left(f\right)}$

我们还是使用之前的例子来验证。

|角度|置换|$m\left(f\right)$|$k^{m\left(f\right)}$| |--|--|--| |$0^{\circ }$| $\{1,2,3,4\}=\left(1\right)\left(2\right)\left(3\right)\left(4\right)$|$4$|$16$| |${90}^{\circ }$| $\{2,3,4,1\}=(1,2,3,4)$|$1$|$2$| |${180}^{\circ }$| $\{3,4,1,2\}=(1,3)(2,4)$|$2$|$4$| |${270}^{\circ }$| $\{4,1,2,3\}=(1,2,3,4)$|$1$|$2$|

从上面的例子中我们发现，$k^{m\left(f\right)}$确实等于$C\left(f\right)$。现在我们的任务只是求出$m\left(f\right)$了。它显然可以$O\left(n\right)$求出：

int flag[10]={0},i,j,m=0;

for(i=1;i<=4;i++)
    if(flag[i]==0) 
    {
        j=i;
        while(flag[j]==0)
            flag[j]=1,j=f[j];
        m++;
    }

所以现在我们可以以$O\left(np\right)$的时间复杂度来求出整个问题的解。其中$p$表示置换数量。

是不是很简单？