(Preface)
初步了解(Polya)定理之后，余便开始研究它的应用。
根据论文里的记载，整理了一下其中的例题。
似乎都是一些远古题库，其中SGU这个题库余竟未曾听说过，而且也找不到（好像已经炸了）。
前置知识
例一：【SGU294 】He's Circles
标签：环 莫比乌斯反演
- 给定一个长度为(n)的环。
- 对它进行黑白染色，问有多少种本质不同的方案。
- 可以旋转得到视为本质相同。
- (nle 2 imes 10^5)
环上(Polya)定理的板子题。
考虑转(i)位置换中环的个数就是(gcd(i,n))，因此答案式为：
看到(gcd)自然而然想到莫比乌斯反演。
因为莫比乌斯反演并非本文的重点，下面的式子可能会比较简略。
枚举(gcd)得到：
容易发现后面就是一个(phi)的形式，得到：
这道题应该是(Polya)定理最基础的应用题了。
例二：【UVA10601】Cubes
标签：立方体 组合数学
- 给定(12)根木棒，每根木棒有一种颜色，且颜色总数不超过(6)。
- 用这些木棒拼成一个立方体，问有多少种本质不同的方案。
- 可以旋转得到视为本质相同。
- 数据组数(le60)。
余的做法
余一开始的想法，就是立方体旋来旋去太麻烦了，不如直接考虑最终结果。
假设(1)号点与(2)号点相连，只要枚举(1)号点的位置（(8)种），再枚举(2)号点与(1)号点的相对位置（(3)种），就能够确定旋转后的立方体了（(8 imes 3=24)种）。
讲道理这个做法应该是正确的，然而这东西并不太好实现，一开始想手打一个表，最后嫌过于繁琐放弃了。
默默点开了题解。。。
题解的做法
考虑立方体的(4)种旋转方式：（本题重点！！！）
- 不动。(1)种方案，每个等价类大小为(1)。
- 绕一组相对顶点旋转。(4)对顶点，每对(2)种方案，每个等价类大小为(3)（同色标出）。
- 绕一组相对的棱转动。(6)对棱，每对仅(1)种方案，(2)个等价类大小为(1)，(5)个等价类大小为(2)。
- 平行转动。(3)个方向，旋转(90°)或(270°)时每个等价类大小为(4)（如图），旋转(180°)时每个等价类大小为(2)（不想画了）。
考虑这题中每种颜色的数量是定死的，因此无法直接套用(Polya)定理，而应该使用(Burnside)引理。
发现除绕一组相对的棱转动的情况以外，其余情况每个等价类大小都是相等的。
而棱的情况其实可以直接暴枚两个大小为(1)的等价类中的元素，则剩下的等价类大小也是相等的。
此时要计算方案数，假设等价类大小都为(x)，如果某个(c_i)（颜色(i)的个数）不是(x)的倍数，显然方案数为(0)。
否则，令所有(c_i)除以(x)，设其总和为(t)，方案数就是可重全排列(frac{t!}{prod c_i!})。
例三：【SPOJ419/SPOJ422】Transportation is (Even More) Fun
标签：环 巧妙转化 莫比乌斯反演
- 给定一个(2^a imes 2^b)的矩阵，要求把它变成它的转置矩阵，但保持矩阵形状不变。
- 每次操作只能交换两个元素，问至少操作几次。
- 询问组数(le100)/询问组数(le4 imes 10^5)，(a+ble10^6)。
什么？说好的(Polya)定理呢？为何画风突变？
把一个位置到它对应位置的转变表示成置换，然后就会发现，设这个置换有(t)个循环，则答案就是(2^{a+b}-t)。
这应该非常显然，因为一个大小为(n)的循环只需操作(n-1)次。
其实呢，若把原序列中的((i,j))表示成(i imes 2^b+j)，而它在转置矩阵中对应的位置就是(j imes 2^b+i)。
如果把(i imes 2^b+j)这个二进制数看成一个环，那么从(i imes 2^b+j)到(j imes 2^b+i)其实就是向右转了(b)位。
于是经转化得到了一个新问题：
- 给定一个长度为(n)的环。
- 对它进行黑白染色，问有多少种本质不同的方案。
- 可经每次旋转(b)位得到视为本质相同。
好嘞，这家伙与(Polya)定理板子的区别仅仅在于每次旋转(b)位。
一个显然的事实，旋转(b)位的等价类个数就是(g=gcd(b,a+b)=gcd(a,b))，且每个等价类大小都为(frac{a+b}g)。
于是可以把一个循环看成一个点，点数就是(n=frac{a+b}g)，颜色数目就是(2^g)。
得到式子：（推导过程可参考例一）
当然别忘了最终答案是(2^{a+b})减去它。
例四：【SGU282】Isomorphism
标签：无向图 除去冗余
- 给定一个(n)个点的无向完全图。
- 把每条边染成(m)种颜色的一种，问有多少种本质不同的方案。
- 可以改变节点编号得到视为本质相同。
- (nle 53,mle1000)
本题中置换群的对象就是这(frac{n(n-1)}2)条边，但由于置换的数量达到(n!)，显然不可以裸暴力。
假设点的置换是(i ightarrow P_i)，则边的置换就是((i,j) ightarrow(P_i,P_j))。
考虑两种置换循环节个数的关系，发现：
- 若点(i,j)属于同一长度为(x)的循环中，((i,j))组成的置换中循环节个数为(lfloorfrac x2 floor)。
- 若点(i,j)分别属于长度为(x,y)的两个循环中，((i,j))组成的置换中循环节个数为(gcd(x,y))。
因此，如果一个点置换长度分别为(L_1,L_2,...,L_s)，则边置换的循环节总数就是：
那么就需要求满足循环节长度为(L_1,L_2,...,L_s)的边置换数目，也就是把(1sim n)放入大小分别为(L_1,L_2,...,L_s)的环的方案数。
如果(L)互不相同，方案数就是：
而若可能有相同的(L)，同样大小的环就会造成重复贡献。
因此假设有(t)种不同的值，并设(C_i)表示第(i)种值的个数，方案数就是：
最终答案就是：（(T,S)的值如上所示，注意这其实是一个(Polya)定理的形式，只是在(m^{c(g_i)})之前乘上了一个方案数）
这道题的核心思想就是把相似的情况放在一起讨论，除去冗余的方法在(Polya)计数问题中是一个很有用的优化。
参考文献
2008 - 陈瑜希《Pólya计数法的应用》
(Postscript)
以上就是对(Polya)定理几种常见模型（环、立方体、无向图）以及优化技巧（莫比乌斯反演、除去冗余）的介绍了。
余希望自己的努力能让更多人认识到(Polya)定理这个美丽的算法。