零.约定：
(置换等名词会在前置知识中有解释）
(1.)在本文中，题目要求的染色方案等统称为“元素”。
(2.)两个元素严格相等我们记做“(=)”，两个元素等价（按题目所给的置换可以互相得到）我们记做“(Leftrightarrow)”。
(3.)元素(a)进行置换(g)我们记做(aotimes g)。
(4.)置换之间的乘积记做(odot)，(g_i=g_jodot g_k)，当且仅当(forall a,aotimes g_i=aotimes g_jotimes g_k)，将(g_jodot g_k)代入(g_i)得(aotimes(g_jodot g_k)=aotimes g_jotimes g_k)。
一.前置知识：
(1.)置换：
如下图所示，这是一个置换，一个置换只与两行之间的对应关系有关，与列的顺序无关。
我们的一个元素(left(egin{matrix}3&2&4&1end{matrix} ight))在经过这个置换后就变成了(left(egin{matrix}4&3&2&1end{matrix} ight))。列({^a_b})表示原来第(a)位的元素置换后到了第(b)位。
(2.)循环：
形式如下的置换叫做一个(n)阶循环（任意一个(n)阶循环可以记做(r_n)）：
(3.)置换的分解：
指把置换(g)分解成(r_1^{k_{1}}r_2^{k_{2}}cdots r_n^{k_{n}})的形式（(r_j^{k_{j}})表示(j)阶循环一共有(k_{j})个（同阶循环可以不相同）），各个循环之间的元素互不相交。感性理解一下就是，对于列(^a_b)，从(a)向(b)连一条有向边，这样会形成一个个环，一个长度为(i)的环对应着一个(r_i)。令(w(g)=sum_{i=1}^n k_i)，即循环总个数。
(4.)不动点：
如果元素(aotimes g_i = a)，那么我们称(a)为置换(g_i)的不动点，(g_i)的不动点个数用(chi(g_i))表示。
(5.)群：
群用((G,oplus))表示，其中(G)是一个集合，(oplus)是定义在(G)上的一个二元运算，并且满足:
封闭性((forall a,b in G,aoplus b in G))
结合律((aoplus(boplus c)=(aoplus b)oplus c))
存在单位元((exists e,forall a,eoplus a = aoplus e = a))
存在逆元((forall a,exists a^{-1},aoplus a^{-1} = a^{-1}oplus a = e))
那么这是一个群。
(6.)置换群：
置换群就是将置换作为元素的群。
证明：
封闭性：置换的乘积也是置换，在这个群中。
结合律：手模小样例可知，(aodot bodot c=aodot(bodot c))。
单位元：
逆元：将置换的两行交换位置便是逆元。
(7.)等价类：
如果(exists g,s.t.~aotimes g = b)那么我们称(aLeftrightarrow b)，所有互相等价的元素组成一个等价类，元素(a)所属的等价类记做(E_a)答案(L)便是等价类的种类。
(8.)不动置换类：
置换群(G)中，使元素(a)不变的置换全体，称为(a)的不动置换类，记做(Z_a(forall g in Z_a,aotimes g=a&&forall g otin Z_a,aotimes g e a))。
二.(Burnside)引理：
内容：
等价类个数
证明：
(step~1:)首先看两个定理：
(1.)
仿佛没什么用的定理：(|Z_k|)是(G)的一个子群。
证明：
封闭性：使(k)不动的两个置换的积也使(k)不动，属于这个群。
结合律：显然。
存在单位元：显然任何元素都(G)单位元的不动点。
存在逆元：置换(g)属于元素(a)的不动置换类，当且仅当(g)的每一列(^x_y)，(a_x=a_y)。显然(g)的逆元也满足这个条件，也在不动置换类中。
(2.)
重要定理：(forall a,|E_a||Z_a|=|G|)
证明：
如果对于(forall bin E_a)都有恰好(|Z_a|)个不同置换使(a)转化成(b)，那么定理得证（因为(a)进行一种置换有且仅有一个结果）。
首先，因为(bin E_a)一定存在一个置换(p)使得(aotimes p = b)。因为(Z_a)是(a)的不动置换类，所以
(forall zin Z_a)
(ecause aotimes z=a,aotimes p = b)
( herefore aotimes zotimes p = b)
( herefore aotimes(zodot p)=b)
(z)互不相同，所以(zodot p)互不相同，(z)有(|Z_a|)种取值，所以有至少(|Z_a|)种置换，使(a)转化成(b)。现在我们只要能证明(zodot p)能够取遍所有使(a)转化成(b)的置换即可。
我们考虑反证法：
同上，因为(bin E_a)一定存在一个置换(p)使得(aotimes p = b)，
假设存在一个置换(q)，(aotimes q = b)，且(forall zin Z_a,zodot p eq q)。
显然(exists c=qodot p^{-1}in G,s.t.~codot p = q)。
(ecause aotimes q =b,codot p = q)
( herefore aotimes(codot p)=b)
( herefore aotimes cotimes p=b)
(ecause aotimes p =b)
( herefore aotimes c = a)
( herefore cin Z_a,)与假设(forall zin Z_a,zodot p eq q)相悖，所以不成立。
证毕。
(step~2:)
设(U)为一个等价类集合，共(L)个等价类。
设(n)是元素总数。
(ecause forall a,|E_a||Z_a|=|G|)
( herefore |Z_a|=frac{|G|}{|E_a|})
( herefore sum_{i=1}^n|Z_i|=|G|sum_{i=1}^nfrac{1}{|E_i|})
因为每个(E_i)大小为(|E_i|)，贡献(frac{1}{|E_i|})，会被算(|E_i|)次，所以每一种等价类的总贡献(1)。(sum_{i=1}^{n}frac{1}{|E_i|}=)等价类的种类即答案(L)。
( herefore sum_{i=1}^n|Z_i|=|G|L)
( herefore L=frac{sum_{i=1}^n|Z_i|}{|G|})
不动点和不动置换的关系是相互的，所有置换的不动点之和等于所有元素的不动置换之和。
( herefore L=frac{sum_{gin G}chi(g)}{|G|})
证毕。
三.(Polya)定理：
内容：
若题目是对(n)个对象染(m)种颜色，则
证明：
若(a)是(g)的不动点，对于每一列(^x_y)，都有(a_x=a_y)，而一个循环是许多列首尾相接，所以他们都相等。所以对于(g)的一个循环(r)，(forall i,jin r,a_i =a_j)，所以(chi(g))就相当于给(g)每个循环染色的方案数（每个循环染相同的颜色）。所以(chi(g)=m^{w(g)})。
证毕。
扩展：
这个式子是基于可以给(g)每个循环任意染色这个前提的，如果染色数量有限制，我们就需要求给(g)每个循环染色的方案数，通常用(dp)来扩展此问题。
四.应用与例题：
常见置换的循环个数：
(1.)（套路(1)）将长度为(n)序列（或者环）循环移(k)位，循环个数为(gcd(n,k))。
(2.)（套路(2)）将长度为(n)环沿对称轴反转，若(n)是奇数则(n)条对称轴的循环个数都是(lceilfrac n 2 ceil)；否则，有(frac n 2)对称轴的循环个数是(frac n 2)，另外一半对称轴个数是(frac n {2}+1)。
例题：
(1.)luogu 1446
(a.)题目大意：
有(n)张扑克牌，染三种颜色，每种颜色规定数目。再给定(m)中洗牌方法，通过洗牌可以互相得到的方案等价，求有多少种不同方案。
(b.)题目分析：
在本题中，洗牌方法就是置换，而染色方案是“元素”。
本题给了 “输入数据保证任意多次洗牌都可用这(m)种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态” 的条件，使满足封闭性和存在逆元。至于单位元，我们需要人为添加一种置换（自己到自己），来使之满足条件，由于单位元(aotimes e = a)的性质，不会对答案产生影响，但我们必须添加使之可以使用(Burnside)引理。
(c.)具体做法：此处染色有数目限制，不能直接使用(Polya)定理。我们首先(Theta(n))求出每一种洗牌方案的循环个数。然后我们对于每一种洗牌方案，通过(dp)求染色方案，具体的说，(f[i][a][b][c])表示前(i)个循环已经染完色，三种颜色分别剩(a,b,c)个
，初始状态(f[0][Sum_a][Sum_b][Sum_c])答案是(f[w][0][0][0])。
总复杂度(Theta(nmSum_aSum_bSum_c))，可过。
(2.)luogu 4980
(a.)题目大意：自己看吧
(b.)题目分析：直接套公式，置换为(n)种循环移位 ，直接套用套路(1)，循环个数为(gcd(n,k))的性质来优化。
我们优化一下：
我们只需要枚举(t)到(sqrt{n})就可以了，然后再(sqrt{n})求(varphi)，复杂的(Theta(Tn^{frac 3 4}))。您也可以大力Pollad-rho一发。
(3.)UVA11255
大水题限制染色次数+可以翻转旋转，直接套用套路(1)、(2)即可。
(4.)UVA10601
(a.)题目大意：一个正方体，给棱染色，有数量限制，旋转同构。
(b.)题目分析：
我们本题置换种类繁多：横向旋转（面向自己的面不变），竖向旋转（面向自己的面发生改变），以及两种旋转的组合。
但是我们发现有一些旋转的组合结果是相同的，我们考虑枚举结果，即选定面向自己的正方形的下底边为基准，枚举原来哪个位置的边转到了这个位置，共十二种置换，然后统计每个置换的循环个数（暴枚或者手模都可以），再根据数量限制扩展一下定理即可。
五.总结：
全是废话
(Polya)定理实质上是(Burnside)引理的一个扩展，虽然式子简单，但是能够解决的问题却很有限。我们通常通过(dp)，组合数等来求不动点个数(chi(g))，这既可以说是(Polya)定理的扩展也可以说是(Burnside)引理的扩展。