这玩意无论学了多少次都跟没学一样(╯°□°)╯︵ ┻━┻
定理
Burnside 引理
其中(L)表示本质不同染色数（轨道数） (G)是置换群 (Z_k)是轨迹 (d_k)是在置换k下的不动的染色种类
Polya定理
其中(m)是颜色数 (c(g_k))是置换(g_k)分解成不相交轮换数量
p.s.: ( ext{Polya定理只有在对所有映射计算的时候才成立 否则不一定成立})
我猜你现在一脸懵 我也懵 我还不想给证明
例题
LOJ6519 魔力环
Shone 喜欢收集黑色与白色的魔力珠。
Shone 希望能够得到一个由 (n)个魔力珠串成的环。不过他对普通的环并不感兴趣，因此他提出了如下的要求：
- Shone 希望在这个环上，恰好有 (m)个黑色的魔力珠与(n-m) 个白色的魔力珠。
- 由于 Shone 认为黑色魔力珠不应过于密集，因此 Shone 希望这个环上不会出现一段连续的黑色魔力珠，其长度超过 (k)。
在 Shone 的心目中，满足上述要求的环才是美妙的。
不过这样的环可能并不唯一。 Shone 想要知道共有多少种不同的环满足他所提出的要求。然而 Shone 并不喜欢计算，他希望聪明的你能够告诉他答案。
在这里，我们认为两个环是不同的，当且仅当其中一个环仅通过旋转无法得到另一个环。
(1le nle 10^5,1le kle 10^5,0le m le n)
思路：
这就是Polya不适合的题【狗头
考虑固定不动点一共有(l)个 那么一共是(frac{n}{l})组 也就是要求(gcd(n,x)=n/l) 这样的(x)有多少呢 就是(phi(frac{n}{n/l})=phi(l))
现在我们就要求(f(x))也就是有 (frac{m}{x})个黑的和(frac{n-m}{x})个白的 构成环【不考虑循环同构】且没有连续(k)个以上黑的的方案数 直接拆环
(F(x,y))表示x个黑的分成y组且没有大于k的方案数 容斥可以计算
计算一个(F(x,y))是(O(x/k))的 计算一个(f(x))是(O(k)) 所以复杂度是(O(sum x))也就是(O(nlgn))【好像远远不到？
代码：戳我
bzoj1478 sgu282 Isomorphism/洛谷4128 [SHOI2006]有色图
给定一个$N $个结点的无向完全图（ 任意两个结点之间有一条边）， 现在你可以用 (M) 种颜色对这个图的每条边进行染色，每条边必须染一种颜色。 若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同， 就称这两个染色方案相同。 现在问你有多少种本质不同的染色方法，输出结果 (mod P)。$P (是一个大于)N $的质数。
(1≤N≤53，1≤M≤1000)
思路：
考虑对于点的置换 拆成循环 内部是(lfloor frac{x}{2} floor)组(a+b=x 的ab是一组) 两个循环之间是(gcd(x,y))组 然后我们考虑直接拆分数枚举然后染色就可以了【Polya定理】
代码：戳我
洛谷4727 [HNOI2009] 图的同构
小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含(N)个点的图有多少种。众所周知含(N)个点的简单图最多有(N*(N-1)/2)条边，这样含(N)个点的图有(2^{N*(N-1)/2})种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！
思路：
考虑图的同构就是把完全图的边黑白染色 然后就和上个题一毛一样了
代码：戳我