CVBB ACM Team

一个n个点的环，用n种颜色去染。求有多少种本质不同的染色方案。

两种染色方案相同当且仅当通过旋转（不包括翻转）后，每个点的颜色都相同。

Polya定理

为了让大家看起来有耐心，我先把结论放出来。事实上，本题的答案是$\frac 1n \sum^n_{i=1} n^{gcd(i,n)}$

但是，想要证明这个结果着实要下一点功夫。事实上，要得到这个答案，需要使用Burnside引理。那么，Burnside引理在说什么呢？

这个引理的内容并不是很通俗易懂，需要先给出一些定义才能表述清楚

n元集合A到它自身的一个一一映射，称为A上的一个n元置换或n阶置换。简记为 \[ \mathbf{\sigma} = \left( \begin{array}{cccc} 1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\\ \end{array} \right) \] 其中，$i_1,i_2,\ldots ,i_n$为1到n的排列

意思是，把第$i_1$个点换到1号位置，第$i_2$个点换到2号位置，……，第$i_n$个点换到n号位置。这个记录方法被称为“两行法”（我自己命名的）。 因为第一行通常为按顺序的1-n，所以经常省略第一行，用$(i_1,i_2,\ldots,i_n)$表示一个n元置换。这个表示方法被称为“一行法”。

我们把对应同一种染色方案的置换称为同种染色置换。全部同种染色置换构成一个集合$G=\{g_1,g_2,\ldots,g_n\}$。本题中，G包含s=n个元素，分别表示顺势针转0~n-1次。定义G上的二元运算*，对$\forall i,j$，$g_i*g_j$表示先按$g_i$置换，再按$g_j$置换。可以证明（参考结论1），$(G,*)$构成一个群，这称为同种染色置换群。

即不考虑旋转情况的染色方案。本问题中共$N=n^n$种朴素染色方案。如无特别说明，此后中的染色方案都指朴素染色方案。可以建立一个正整数到染色方案的一一映射，即可以用一个1~N的正整数表示一种染色方案。

对一种同种染色置换$g（g\in G）$和每一种染色方案k（$1\le k\le N$），g(k)也是一个1~N的整数,表示另一种染色方案，即将染色方案k按照g进行置换。从k到g(k)的映射称为g对k的作用。特别注意，g(k)可能等于k（如k表示将所有点染成红色，则无论怎么旋转，显然染色方案不变），也可能不等于k。但无论g(k)与k是否相等，g(k)与k都是本质相同的染色（因为是同种染色置换得到的，在最终答案中只考虑一次）。

介绍了这么多，终于可以阐述Burnside引理的内容了。首先，构造一个函数$\forall g\in G，x\in \{1,2,\ldots,N\}，f(g,x)=[g(x)=x]$。这是一个典型的用于计数的函数。设$h(g_i)=\sum^N_{k=1}f(g_i,k)$，即满足$g_i(k)=k$的染色方案个数。那么最终答案$ans=\frac 1s\sum^s_{i=1}h(g_i)$，其中$s=|G|$

(G,*)构成一个群。

根据群的定义，满足封闭性，结合律，单位元，逆元四条性质的集合和二元运算构成群（四条性质具体内容不了解的可以百度）。

显然，G对*运算满足封闭性，结合律。单位元e即旋转0次对应的置换。除e以外，旋转i次置换的逆元为旋转n-i次置换。

事实上，这是Burnside引理基本的适用范围。也就是说，只有同种染色置换能构成群的问题，才能使用Burnside引理来解决。

对于任意染色方案k，G中一定存在一些元素满足g(k)=k（至少e一定满足要求，因此“一定”的表述的严谨的）。设所有满足g(k)=k的同种染色置换构成k的不动点集，用$Z_k$表示。可以证明，$(Z_k,*)$构成一个群（结合律，单位元显然，封闭性，逆元也易证）。

对将G中的s个元素分别作用于k，得到k的等价类，用符号$E_k$表示。$E_k=\{g_1(k),g_2(k),\ldots,g_s(k)\}$包含全部本质上和k相同的朴素染色方案。特别注意，$g_1(k),g_2(k),\ldots,g_s(k)$中存在一些相同的数，应当剔除重复的结果，得到$E_k$。

设$E=\{k_1,k_2,\ldots,k_m\}$，显然有$E=E_{k_1}=E_{k_2}=\ldots=E_{k_m}$

我们最终要计算有多少种本质不同的染色方案，其实就是要计算一共有多少个等价类。

对1~N中的任何一个数k，有$|G|=|E_k|\cdot |Z_k|$

设$Z_k=\{g_{i_1},g_{i_2},\ldots,g_{i_p}\},E_k=\{g_{j_1}(k),g_{j_2}(k),\ldots,g_{j_q}(k)\}$

设$H=\{g|g=g_{i_x}*g_{j_y},1\le x \le p,1\le y \le q\}$。若y不相等，则$g(k)=g_{j_y}(g_{i_x}(k))=g_{j_y}(k)$不相等。若y相等且x不相等，则$g*g_{j_y}^{-1}=g_{i_x}$不相等。因此有H中任意两个元素都不相同，H中共有$pq$个元素。

显然有$H\subseteq G$，下证$G\subseteq H$。

对G中任意元素g,有$g(k)\in E_k$，设$g(k)=g_{j_y}(k)$。则有$g_{j_y}^{-1}(g(k))=k$，即$g*g_{j_y}^{-1}\in Z_k$。则有$g_{i_x}=g*g_{j_y}^{-1}$，$g=g_{i_x}*g_{j_y}\in H$。所以$G\subseteq H$。

所以有$G=H$。

因为$|H|=pq=|E_k|\cdot |Z_k|$，所以$|G|=|E_k|\cdot |Z_k|$

这个结论证明了，对一个等价类$E=\{k_1,k_2,\ldots,k_m\}$，有$\sum^m_{i=1}|Z_{k_i}|=|G|$

$f(g,x)$和$h(g_i)$的定义见Burnside引理。接下来将开启一波愉快的推式子。

$\sum^s_{i=1}h(g_i)=\sum^s_{i=1}\sum^N_{x=1}f(g_i,x)=\sum^N_{x=1}\sum^s_{i=1}f(g_i,x)=\sum^N_{x=1}|Z_x|$

这道题求的答案$ans$是等价类个数。

由结论2，$\sum^N_{x=1}|Z_x|=ans\cdot |G|$。所以$ans=\frac 1s\sum^s_{i=1}h(g_i)$，其中$s=|G|$

希望大家没有忘记原先的问题。如果忘了，可以回到最上面看一下。

在这个问题当中，我们最重要的就是求出$c(g_i)$。我们不妨先从简单的情况想起。我们设$g_i$表示顺势针转i次的置换。显然有，$c(g_0)=N=n^n$，也就是说，对$\forall k,g_0(k)=k$。

同样的，显然有$c(g_1)=n$，只有所有点颜色都相同的朴素染色方案，才有顺势针旋转1次后，结果不变。

对于旋转i次，要求第1个点，第1+i个点，第1+2i个点,…,第ki%n+1个点颜色必须相同。所有形如(ki+1)%n+1的点颜色必须相同；形如(ki+2)%n+1的点必须相同……由裴蜀定理一共有$gcd(n,i)$组点，每组点的颜色必须相同。因此，$c(g_i)=n^{gcd(n,i)}$

所以，这个问题的答案$ans=\frac1n \sum^n_{i=1} n^{gcd(n,i)}$

所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。

形如$5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$的（首尾相同，中间无重复）链，称为一个循环。这个循环表示将5换到1的位置、1换到2的位置、2换到3的位置、3换到4的位置、4换到5的位置，记作$(5,1,2,3,4)$，称为5元循环。

一个循环中所包含的数，称为这个循环的元素。

对于一个置换，除了用“两行法”，“一行法”表示，还有一种“循环法”。“循环法”描述一个置换所包含的全部循环。比如“一行法”表示的置换$(5,1,2,3,4)$，包含一个循环$5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$，可以用一个括号，里面描述这个循环。“一行法”表示的$(5,1,2,3,4)$用“循环法”表示仍是$(5,1,2,3,4)$。再比如$(5,3,2,1,4)$，包含$5\rightarrow 1\rightarrow 4\rightarrow 5$和$3\rightarrow 2\rightarrow 3$，这两个循环。因此，$(5,3,2,1,4)用“循环法”可以记作(5,1,4)(3,2)$。

值得注意的是，仅改变括号顺序，并不改变置换。如$(1,2)(3,4)(5)$和$(3,4)(5)(1,2)$均表示$(2,1,4,3,5)$。每个括号内数字的轮换也不改变置换，如“循环法”表示的$(5,1,2,3,4)，(2,3,4,5,1)，(1,2,3,4,5)$均表示“一行法”下的$(5,1,2,3,4)$。但交换一个括号内的两个数，可能会改变置换。如$(5,1,4)(3,2)$表示$(5,3,2,1,4)$，而$(1,5,4)(3,2)$表示$(4,3,2,5,1)$。

可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，每个循环都确定。

一个置换所包含的循环的个数，为该置换的循环数。如$(1,2)(3,4)(5)$的循环数为3，$(1,5,4)(3,2)$的循环数为2，$(5,1,2,3,4)$的循环数为1

对于任意置换g，设c(g)表示其循环数。

假设所求问题为n个点染m种颜色。对于任意置换$g_i$，有$h(g_i)=m^{c(g_i)}$，其中$h(g_i)$为置换$g_i$的不动点数，$c(g_i)$为置换$g_i$的循环数。

对任意染色方案k，$g_i(k)=k$当且仅当$g_i$的每个循环中所有元素颜色均相同。如k满足$g_i=(1,5,4)(3,2)$，$g_i(k)=k$当且仅当第1,4,5个点颜色相同，第2,3个点颜色相同。因此有$h(g_i)=m^{c(g_i)}$

将结论4带入Burnside引理，得$ans=\frac 1s\sum^s_{i=1}h(g_i)=\frac 1s\sum^s_{i=1}m^{c(g_i)}$