群：$(G,\times)$ 集合与作用于其的二元运算，具有封闭性，结合性，单位元以及逆元。

$T$ 的左陪集 $gT$：$g\in G,T\subseteq G$，把置换 $g$ 作用到子群 $T$ 得到的新子群，可能不是 $G$ 的子群。若 $g\in T$，则由封闭性得 $gT=T$，逆向同理。

$G/T$：$G$ 中所有 $T$ 的左陪集，$[G:T]$ 即 $|G/T|$。

左群作用：把群 $G$ 的作用效果以一定方式推广到一个集合，虽然集合不一定具有群的性质。对于集合 $S$ 的任意元素 $a$，若存在 $u,v\in G$，单位元 $e$ 有 $G\times S\to S$ 记作二元运算 $\circ$ 满足：

$$ e\circ a=a\\ (v\times u)\circ a=v\circ (u\circ a) $$

拉格朗日定理：群 $T\subseteq G$，则 $|T|\times [G:T]=|G|$。

• $g\in G$，则 $|gT|=|T|$，用逆元证。
• $\forall g_1,g_2\in G$，$g_1T\cap g_2T=\varnothing$ 或 $g_1T=g_2T$，设 $v\in g_1T,v\in g_2T$，则 $g_1^{-1}\times v\in T,g_2^{-1}\times v\in T$，$g_1^{-1}\times v\times (g_2^{-1}\times v)^{-1}=g_1^{-1}\times g_2\in T$，利用陪集性质有 $(g_1^{-1}\times g_2)T=T,g_1T=g_2T$，不存在 $v$ 则交集为空。
• $gT\subseteq G$，由群的封闭性显然。
• 由此可知 $G$ 中所有 $T$ 的左陪集 $|gT|=|T|$，且互不相交，则这些陪集的并就是 $G$，若 $u\in G$ 不在陪集中出现，则任意选取一个 $v\in T$，则 $u\in (v^{-1}\times u)T$ 在陪集中出现了。

轨道-稳定子定理：群 $T$ 作用在集合 $S$ 上，$x\in S$，记 $T^x$ 为 $T$ 中作用于 $x$ 上使其不改变的元素集合，该集合称为 $x$ 的稳定子；$T(x)$ 为 $T$ 中所有元素作用在 $x$ 上得到的集合，该集合称为 $x$ 的轨道。定理指出 $|T^x|\times |T(x)|=|T|$ 对任意 $x\in S$ 成立。

• $T^x\subseteq T$，封闭：$\forall a,b\in T^x,a\circ x=b\circ x = x$，由群作用性质有 $(a\times b)\circ x=a\circ(b\circ x)=x$，则 $a\times b\in T^x$；结合律由群性质显然；单位元 $e\circ x=x,e\in T^x$；逆元由于 $e\in T^x$，$\forall e\in T^x,e\circ x=(a^{-1}\times a)\circ x=a^{-1}\circ(a\circ x)=x$，则存在逆元 $a^{-1}$。由此 $T^x$ 是 $T$ 的子群。
• 用拉格朗日定理改写为 $|T^x|\times [T:T^x]=|T|$，需要证明 $[T:T^x]=|T(x)|$，尝试建立双射，对于 $g\in T$，用 $gT^x$ 对应一个稳定子群的陪集，对于轨道中的相同元素 $f\circ x=g\circ x$，左乘 $g^{-1}$ 得到 $(g^{-1}\times f)\circ x=e\circ x,g^{-1}\times f\in T^x,(g^{-1}\times f) T^x=T^x,fT^x=gT^x$，反向则是 $fT^x=gT^x,g^{-1}\times f\in T^x,f\circ x=g\circ x$，即建立了一个轨道元素与 $T$ 的左陪集之间的双射。

Burnside 引理：若 $x,y\in S$，且存在 $g\in T$ 满足 $g\circ x=y,g^{-1}\circ y=x$，称 $x,y$ 本质相同，$S/T$ 表示在群 $T$ 的作用下把集合 $S$ 分为的本质不同的每种种类元素集合的集合，记 $S^g$ 表示 $g$ 作用下 $S$ 中不改变的元素集合，则 $|S/T|=\frac{1}{|T|}\sum_{g\in T}|S^g|$，即 $|S/T|=\frac{1}{|T|}\sum_{x\in S}|T^x|$。

$$ \begin{align} &\frac{1}{|T|}\sum_{x\in S}|T^x|\\ =&\sum_{x\in S}\frac{|T^x|}{|T|}=\sum_{x\in S}\frac{1}{|T(x)|}\\ =&\sum_{G\in S/T}\sum_{x\in G}\frac{1}{|T(x)|}=\sum_{G\in S/T}\sum_{x\in G}\frac{1}{|G|}\\ =&\sum_{G\in S/T}1=|S/T| \end{align} $$

其核心在于每种颜色不相交，以及同种颜色中每个元素的轨道都为该颜色集合，也可以表述为不动点的平均数。

注意挖掘 $|S/T|$ 的实际含义，比如在染色问题中以一种染色方案作为 $S$ 中的元素，同构的置换构成群 $T$，则 $|S/T|$ 代表在此同构意义下的染色方案数，需要考虑把同构用群来描述。

Pólya 定理：研究对 $S$ 中的元素染色，$T$ 作用下本质不同的染色方案数，设 $c(g)$ 为 $g$ 中的轮换个数，$N$ 为颜色集合，则有 $|S/T|=\frac{1}{|T|}\sum_{g\in T}|N|^{c(g)}$。

只需要证明 $|N|^{c(g)}=|S^g|$，把轮换看作环，$S^g$ 中必然是每个环染相同的颜色，则每个环的方案数是 $|N|$，总的就是 $|N|^{c(g)}$。

LGP4980：【模板】Pólya 定理，$n$ 个点的环，仅旋转同构，$n$ 种颜色染色求方案数，$1\leq T\leq 10^3,1\leq n\leq 10^9$。

循环置换构成的群按照旋转长度有 $0\sim n-1$ 共 $n$ 个，则方案数 $|S/T|=\frac{1}{n}\sum_{i=0}^{n-1}n^{c(p_i)}$，其中 $p_i$ 是旋转长度为 $i$ 的循环置换，$u\to u\bmod n+i$ 成若干环，一个轮换经过若干全长 $n$，同时也是若干步长 $i$，因此一个轮换的长度是 $\operatorname{lcm}(i,n)$，总长是 $i\times n$，则轮换个数 $c(g)=\frac{i\times n}{\operatorname{lcm}(i,n)}=\gcd(i,n)$，认为 $0$ 和 $n$ 等价更方便计算。

$$ \begin{align} &\frac 1 n\sum_{i=1}^n n^{(i,n)}\\ =&\frac 1n\sum_{d=1}^nn^d\sum_{i=1}^n[(i,n)=d]\\ =&\frac 1n\sum_{d|n}n^d\sum_{i=1}^{\frac nd}[(\frac id,\frac nd)=1]\\ =&\frac 1n\sum_{d|n}n^d\varphi(\frac nd)\\ \end{align} $$

$$ n=\prod p_i^{e_i}\\ \varphi(n)=\prod \varphi(p_i^{e_i})=n\prod (1-\frac{1}{p_i}) $$

POJ2409：翻转同构，旋转同构环染色计数，$n$ 个位置，$c$ 种颜色。Polya 定理。

旋转同构共 $n$ 种，$c(g)$ 分别为 $\gcd(i,n)$，翻转同构分奇偶：

• 奇数共 $n$ 种，$c(g)$ 为 $\frac{n+1}{2}$；
• 偶数共 $n$ 种，其中以对边为对称轴的有 $\frac n2$ 种，$c(g)$ 为 $\frac n2$，剩余以对点作为对称轴，$c(g)$ 为 $\frac n2+1$。

$$ \frac 1{2n}(\sum_{i=1}^n c^{(i,n)}+一堆c^{c(g)}) $$

HDU1812：旋转同构，翻转同构棋盘染色计数，$n\times n$ 的棋盘，$c$ 种颜色。Polya 定理。

旋转同构：

• 顺时针 0°，$c(g)=n^2$；
• 顺时针 90°，$c(g)=f(n),f(1)=f(2)=1,f(n)=f(n-2)+n-1$；
• 顺时针 180°，奇数时 $c(g)=\frac{n^2+1}{2}$，偶数时 $c(g)=\frac{n^2}{2}$；
• 顺时针 270°，$c(g)=f(n)$。

翻转同构：

• 对边翻转，共两种，奇数 $c(g)=\frac{n(n+1)}{2}$，偶数 $c(g)=\frac{n^2}{2}$；
• 对角线翻转，共两种，$c(g)=\frac{n(n+1)}{2}$；

$|T|=4+2+2=8$。

UVA10601：给定 12 根棱的颜色，旋转同构，立方体计数。Burnside 引理。

讨论置换群 $T$：

• 不动，1 种，$(1)^{12}$；
• 沿着对面旋转 90°，6 种，$(4)^3$；
• 沿着对面旋转 180°，3 种，$(2)^6$；
• 沿着对棱中点连线旋转 180°，6 种，$(1)^2(2)^5$；
• 沿着对顶点连线旋转 120°，2*4=8 种，$(3)^4$，可以看作两个顶点所在的三个面分别转。

$|T|=24$。

在 Burnside 引理中，$S^g$ 表示 $g$ 作用下不改变的染色方案集合，这里要求每个环的颜色都相同，方案数是 $\frac{s!}{\prod c_i!}$，其中 $s$ 是环的数量，$c_i$ 是颜色 $i$ 可以完整染的环数量，这个式子要求每个环大小都相同。

对于大小都为 $x$ 的情况，有 $c_i$ 个的 $i$ 颜色可以处理 $\lfloor \frac{c_i}x\rfloor $ 个环，于是贡献是 $\frac{\frac{12}{x}!}{\prod \lfloor \frac{c_i}x\rfloor!}$。

而对于 $(1)^2(2)^5$ 的情况，可以枚举两个 1 放什么再相同处理。

UVA11255：限制三种颜色分别使用 $a,b,c$ 次，翻转同构，旋转同构，环染色计数。

$n=a+b+c$。与上一题类似的，考虑 $|S^g|$。

翻转同构：

• 奇数有 $n$ 种，$(1)^1(2)^{\frac{n-1}{2}}$；
• 偶数有 $\frac n2$ 个 $(2)^{\frac n2}$，$\frac n2$ 个 $(1)^2(2)^{\frac n2 -1}$。

旋转同构：

• 对于 $1\leq i\leq n$，都有一种循环置换 $p_i$，其所有环长相等，有 $\gcd(i,n)$ 个环，则可以视作 $(\frac{n}{(i,n)})^{(i,n)}$。

类似上一题计算即可。

HDU2481：正 $n$ 边形在中心放一个连接所有顶点的点，旋转同构，要求去掉 $n$ 条边后连通，计数。$3\leq n,p\leq 10^9$。Burnside 引理，矩阵乘法，差分。

不考虑旋转同构，FJOI2007 轮状病毒，不跨过 $1-n$ 的方案数即设 $f_i$ 是已经有 $i$ 个周围点方案数，$f_i=\sum_{j=1}^i f_{i-j}\times j$，即加入一批 $j$ 个点，并任选一个和中心相连，考虑跨过的方案数即 $g_i=\sum_{j=1}^i f_{i-j}\times j\times (j-1)$，即选择 $j$ 个点固定跨越 $1-n$，有 $j-1$ 种选法，选出来之后再任选一个和中心相连，答案就是 $f_n+g_n$。为了快速求，差分一下：

$$ f_i-f_{i-1}=\sum_{j=1}^i f_{i-j}\times j-\sum_{j=1}^{i-1}f_{i-1-j}\times j\\ =\sum_{j=0}^{i-1}f_j\times (i-j)-\sum_{j=0}^{i-2}f_{j}\times (i-1-j)\\ =\sum_{j=0}^{i-1}f_j $$

也就是 $s_i=\sum_{j=1}^i f_i,f_i=f_{i-1}+s_{i-1}$。

同样的，我们对 $g$ 也尝试差分一下：

$$ g_i-g_{i-1}=\sum_{j=1}^i f_{i-j}\times j\times (j-1)-\sum_{j=1}^{i-1}f_{i-1-j}\times j\times (j-1)\\ =\sum_{j=0}^{i-1}f_j\times (i-j)\times(i-j-1)-\sum_{j=0}^{i-2} f_j\times (i-j-1)\times(i-j-2)\\ =2\times \sum_{j=1}^{i-1}f_j\times(i-j-1)\\ $$

不太优美，我们记 $d_i=\sum_{j=1}^{i-1}f_j\times(i-j-1)$，对 $d$ 再进行一次差分：

$$ d_i-d_{i-1}=\sum_{j=1}^{i-1}f_j\times(i-j-1)-\sum_{j=1}^{i-2}f_j\times(i-j-2)\\ =\sum_{j=1}^{i-2} f_j=s_{i-2} $$

很棒！$g$ 的二阶差分是与 $f$ 的前缀和相关，那么我们有：

$f_i=f_{i-1}+s_{i-1},s_i=s_{i-1}+f_i,d_i=d_{i-1}+s_{i-2}=d_{i-1}+s_{i-1}-f_{i-1},g_i=g_{i-1}+2\times d_i$，答案 $F_n=f_n+g_n$

至此我们可以用四个数组完成只和前一项有关的线性递推，也就可以用矩阵快速幂来加速转移了。

回到此题，考虑类似环染色计数套一个 Burnside 引理，根据循环置换长度有置换 $p_{1\cdots n}$，$p_i$ 的轮换个数是 $\gcd(i,n)$，一个稳定子需要满足其应用置换后是不发生改变的，也就是每个轮换的状态都要相同（向左右连或向中心连），方案数即为 $\gcd(i,n)$ 个点不考虑旋转同构的答案。

于是这题的答案就是 $\frac 1n\sum F_{\gcd(i,n)}=\frac 1n\sum F_d\times \varphi(\frac nd)$，利用矩阵快速幂加速转移即可。

注意模数可能不和 $n$ 互质，于是只能把模数变为 $n\times p$，最后除以 $n$ 再$\bmod p$，需要快速乘。

POJ2888：旋转同构，环染色计数，$k$ 对限制 $a,b$ 颜色不能相邻，$n\leq 10^9$ 个位置，$m\leq 10$ 种颜色。

注意到颜色数不对劲，Burnside 一手，直接要求在旋转 $1\leq i\leq n$ 步下相同，也就是共 $\gcd(i,n)$ 个轮换，每个轮换颜色相同，相邻两个属于同一轮换的位置之间合法则全局合法，直接设 $f_c$ 是当前结束颜色是 $c$ 的方案数，钦定第一个位置的颜色，矩阵快速幂 $i$ 轮即可，答案还是 $\frac 1n \sum F_d\times \varphi(\frac nd)$ 的形式。

HDU2865：旋转同构，环连中心染色，相邻点颜色不同，$n$ 位置 $c$ 颜色，$n,c\leq 10^9$。

想复杂了，不要去枚举环上用了多少个颜色，直接只给环 $c-1$ 个颜色再把答案乘 $c$ 就好了，同洛谷模板。

HDU3479：有长度为 $n$ 的序列 $A,C$ 和排列 $B$，给定序列 $C$，数一数有多少个 $A$ 存在某个 $B$ 满足 $A_{B_i}=B_{C_i}$。$n\leq 30$，多测。

好像是巨大牛逼题，不会，mark 个文字题解 https://www.docin.com/p-209298308.html。

SP422：旋转 $b$ 单位同构，环染色计数，$a+b$ 个位置，两种颜色。

若同构，以 $b$ 单位旋转相同，共 $\gcd(a+b,b)=\gcd(a,b)$ 个轮换，每个轮换长度 $\frac{a+b}{\gcd(a,b)}$，把相邻 $\gcd(a,b)$ 个位置看作一个完整的位置，则变为了旋转 1 单位同构，现在 $n=\frac{a+b}{\gcd(a,b)}$，$|N|=2^{\gcd(a,b)}$，直接套 Polya 即可，答案是 $2^{a+b}$ 减去 $\frac 1n \sum_{i=1}^n |N|^{\gcd(i,n)}=\frac 1n \sum_{d|n} |N|^d\varphi (\frac nd)$。

数据范围加大本质做法不变，枚举因子聪明一点即可。