polya定理

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

问题

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

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

暴力

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

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

bunside引理

bunside引理是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\}$

接下来就是bunside引理了：

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

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

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

polya定理

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

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

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

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

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

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

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

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(np)$的时间复杂度来求出整个问题的解。其中$p$表示置换数量。

是不是很简单？