不杂题不选做，week4

yzy4090 · 2025-06-11 13:28:02 · 个人记录

Day1

CF166B Polygons

人机题。全部求个凸包，看是不是 A。

P4250 [SCOI2015] 小凸想跑步

把概率换成所有站位正确的点构成的集合面积与操场面积的比值。
然后就是大力推导。设凸多边形 Q=\left<Q_1,Q_2,\dots Q_n\right>，P 点满足对于所有的 1\le i\le n，简记 j=i\bmod n+1，都有 S_{\triangle PQ_1Q_2}\le S_{\triangle PQ_iQ_j}（取不取等无所谓）。
记 Q_1,Q_2,Q_i,Q_j,P 的 x,y 坐标为 x,y 两字母加上和它相同的下标，如 Q_j(x_j,y_j)，那么有：

y(x_1-x_2-x_i+x_j)+x(-y_1+y_2+y_i-y_j)+(x_iy_j-y_ix_j+y_1x_2-x_1y_2)\ge 0

再加上 P 必须在 Q 内部的限制，就是一个正常的半平面交问题了。

CF720D Slalom

看上去像是 dp，但是若状态中仅考虑目前的位置的话是难做的，会有很多相同的方案重复计算。面对这些重复方案一般有两种处理手段：把它们通过某些容斥减去，或是把它们变成不合法的。
本题考虑后一种，将最低的路径看作所有相同路径的代表路径。
那么设 dp_{i,j} 表示到 (i,j) 的代表路径条数，按列从左到右考虑。有两种转移：

若下方未出现一个矩形，则 dp_{i,j}=dp_{i-1,j}。
若下方出现一个矩形，则 \displaystyle dp_{i,j}=\sum_{k=pos}^j dp_{i-1,k}，其中 k 是满足 dp_{i-1,k} 向上直到 dp_{i-1,j} 都没有矩形的最小的 k。

考虑维护 i-1 有哪些地方有矩形，然后对所有矩形顶上的位置修改成上述和，别的不用改。虽然是时刻维护的 dp_{i,j}，但是由于只用改 \mathcal O(n) 次，时间复杂度是 \mathcal O(n\log n) 的。

P3823 [NOI2017] 蚯蚓排队

人机题。
发现 k\le 50，于是用链表维护队伍，记录每个队伍的前 k 个和后 k 个哈希值，然后合并和分裂时暴力算，做到 \mathcal O(1) 计算即可。可以手写哈希表。
证明这个东西的复杂度。一次分裂一定是 \mathcal O\!\left(k^2\right) 的；考虑仅合并时，对于一只蚯蚓的向后 k 数字串，从没有到有后就不会再发生变化，所以总体的时间复杂度是 \mathcal O(nk) 的。查询的时间复杂度为单次 \mathcal O(|S|)。总体计算一下时间复杂度是 \mathcal O\!\left(nk+ck^2+\sum|S|\right)，由于额外的限制 c\le 1000，这是可接受的。

Day2

P5471 [NOI2019] 弹跳

有一个边数很多的图，要跑单源最短路，那么一般的想法就是用个什么数据结构优化建图。这题自然能想到 KDtree，但是边数是 \mathcal O(m\sqrt n) 的，存都存不下。
考虑 dijkstra 的特性，最有用的就是每个点只会被扩展一次。也就是说，现在要做的事是找到离原点最近的点，以及对于一个矩形，取出所有的未被扩展的点。
不难发现两件事都与矩形相关，所以索性不拆它了，而是在它上跑最短路。每次找到矩形中所有未被扩展的点，对它指向的所有矩形松弛。维护一个线段树，其中每个节点都用 std::set 维护所有 x 坐标在区间 [l,r] 中的点，询问时二分出所有需要的节点就行。这样的时间复杂度是两个 \log 的。
有单 \log 的做法，见文章。

P9478 [NOI2023] 方格染色

人机题。
先把斜线有交的合成一条。对于一条斜线，先把可能与横平竖直的线相交的部分拿出来变成单点，然后把它们合在一起扫描线，加上绝对会产生贡献的点数就做完了。时间复杂度 \mathcal O(kq\log q)，其中 k 是斜线个数。

Day3

P4389 付公主的背包

若单个物品的体积为 v，则其生成函数为

F(x)=1+x^v+x^{2v}+\cdots=\frac{1}{1-x^v}

把它们乘起来就是完全背包的生成函数了。直接乘时间复杂度不对，但是可以通过 \ln 将乘法转为加法。首先有

\ln F(x)=G(x)\Longleftrightarrow \frac{F'(x)}{F(x)}=G'(x)

由于

\begin{aligned}F'(x)&=\sum_{i=1}ivx^{iv-1}\end{aligned}

因此

\begin{aligned}G'(x)&=\left(1-x^v\right)\sum_{i=1}ivx^{iv-1}\\&=\sum_{i=1}ivx^{iv-1}-\sum_{i=1}ivx^{(i+1)v-1}\\&=\sum_{i=1}ivx^{iv-1}-\sum_{i=2}(i-1)vx^{iv-1}\\&=\sum_{i=1}vx^{iv-1}\end{aligned}

于是

G(x)=\sum_{i=1}\frac{x^{iv}}{i}

将同样大小的商品合成一件，预处理 \sum G(x)，然后 \exp。时间复杂度是 \mathcal O(m\log m) 的。

P4091 [HEOI2016/TJOI2016] 求和

第二类斯特林数 \begin{Bmatrix}n\\k\end{Bmatrix} 指将 n 个不同物品放进 k 个相同的盒子，没有盒子空置的方案数。
可以得到递推式：

\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}

逐步把限制放宽，得到 f_i 表示将 n 个不同物品放进 i 个不同的盒子，没有盒子空置的方案数；g_i 表示允许空置盒子的方案数。那么有

g_i=i^n=g_i=\sum_{j=0}^i\binom{i}{j}f_j

由二项式反演得

f_i=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}g_j=\sum_{j=0}^i\frac{j^n(-1)^{i-j}i!}{j!(i-j)!}

于是有

\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{f_k}{k!}=\sum_{i=0}^k\frac{i^n(-1)^{k-i}}{i!(k-i)!}

回到本题的式子。先把 j 提前，然后把 \begin{Bmatrix}i\\j\end{Bmatrix} 拆开：

\begin{aligned}&\ \ \ \ \ \sum_{j=0}^n2^jj!\sum_{i=j}^n\sum_{k=0}^j\frac{k^i(-1)^{j-k}}{k!(j-k)!}\\&=\sum_{j=0}^n2^jj!\sum_{i=j}^n\sum_{k=0}^j\frac{(j-k)^i(-1)^{k}}{(j-k)!k!}\\&=\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\sum_{i=j}^n\frac{(j-k)^i}{(j-k)!}\\&=\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{\sum_{i=j}^n(j-k)^i}{(j-k)!}\end{aligned}

做一些手段使得 i 可以从 0 开始枚举，那么有

\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!}\\=\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!}

可以发现后面一堆式子形似卷积，直接做就是了。

P4705 玩游戏

前置的前置：P4721 【模板】分治 FFT

把题中限制换种说法，由于最终 F 在 \bmod\ x^n 的域中已无法再扩张，因此 F=FG+1。于是 F=(1-G)^{-1}，直接上多项式求逆。
但这是不好的。着实需要学习分治 FFT。
最终的目标是考虑所有 (i,j)(i<j) 对的贡献。类似 cdq 分治地先递归左侧再递归右侧，中途计算所有左对右的贡献。这是两个 \log 的。
EI 文章中有更好的做法。

upd：现在可以看这里了。

前置：P7431 [THUPC 2017] 小 L 的计算题

找到 f_i 的生成函数 F(x)：

\begin{aligned}F(x)&=\sum_{k=0}f_kx^k\\&=\sum_{k=0}x^k\sum_{i=1}^na_i^k\\&=\sum_{i=1}^n\sum_{k=0}(a_ix)^k\\&=\sum_{i=1}^n\frac{1}{1-a_ix}\end{aligned}

考虑 \frac{A}{B}+\frac{C}{D}=\frac{AD+BC}{BD}，两边分治后将两个分数通分，时间复杂度可以用类似分治 FFT 的方式计算，也是 \mathcal O\!\left(n\log^2 n\right) 的。
也可以注意到通分后分子就是负的分母求导后的结果。经检验上面那种常数过大过不去，而这个可以。

对于原题，看起来就和上题比较像。需要计算

\frac{\ \underset{i=1}{\overset{n}{\sum}}\underset{j=1}{\overset{m}{\sum}}(a_i+b_j)^k\ }{nm}

在 k=1,2,\dots,t 情况下的值。仅看分子，用二项式定理拆开得到

\begin{aligned}\underset{i=1}{\overset{n}{\sum}}\underset{j=1}{\overset{m}{\sum}}(a_i+b_j)^k&=\sum_{i=1}^n\sum_{j=1}^m\sum_{l=0}^k\binom{k}{l}a_i^lb_j^{k-l}\\&=k!\sum_{l=0}^k\left(\frac{1}{l!}\sum_{i=1}^na_i^l\right)\!\left(\frac{1}{(k-l)!}\sum_{i=1}^mb_i^{k-l}\right)\end{aligned}

这样就变成了两个上面的问题，直接做就行。
注意本题需要计算 \sum a_i^0,\sum b_i^0，而上题不需要。

Day4

P6055 [RC-02] GCD

由于 i 仅对 j 有限制，所以先把它放在一边。然后 j 相当于是在枚举二元组 (P,Q) 的 \gcd，从而有 p=\frac{P}{j},q=\frac{Q}{j},\gcd(p,q)=1。
于是式子可以变形：

\begin{aligned}\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\left\lfloor\frac{n}{j}\right\rfloor}\sum_{q=1}^{\left\lfloor\frac{n}{j}\right\rfloor}[i\perp j][p\perp q]&=\sum_{i=1}^n\sum_{j=1}^n\sum_{P=1}^n\sum_{Q=1}^n[i\perp j][\gcd(P,Q)=j]\\&=\sum_{i=1}^n\sum_{P=1}^n\sum_{Q=1}^n[\gcd(i,P,Q)=1]\\&=\sum_{i=1}^n\sum_{P=1}^n\sum_{Q=1}^n\sum_{g|i,P,Q}\mu(g)\\&=\sum_{g=1}^n\mu(g)\left\lfloor\frac{n}{g}\right\rfloor^3\end{aligned}

用杜教筛就做完了。

P4491 [HAOI2018] 染色

卷积优化二项式反演。
把“恰好有 i 种颜色”换成“钦定 i 种颜色”，记前者的方案数为 f_i，后者的为 g_i，则答案为 \sum f_iW_i。
由二项式反演得

f_i=\sum_{j=i}^m(-1)^{j-i}\binom{j}{i}g_j

可以直接计算 g_i，具体而言可以先钦定 i 种颜色是什么，然后内部是一个 multinomial，外面的颜色任选。结果为

g_i=\binom{m}{i}\frac{n!}{(S!)^i(n-Si)!}(m-i)^{n-Si}

直接做时间复杂度是 \mathcal O\left(m^2\right) 的。把二项式反演中的二项式系数拆开得

f_i=\sum_{j=i}^m(-1)^{j-i}\frac{j!}{i!(j-i)!}g_j\\f_i=\frac{1}{i!}\sum_{j=i}^m\frac{(-1)^{j-i}}{(j-i)!}j!g_j

后面的式子可以看作是某种“差卷积”，做的时候只需要翻转下标即可。这样的时间复杂度是 \mathcal O(n+m\log m)。

Day5

P5395 第二类斯特林数·列

上文中提到第二类斯特林数的计算公式：

\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{i^n}{i!}\frac{(-1)^{k-i}}{(k-i)!}

这是个卷积的形式，可以做行版本的。
对于本题，考虑找到其生成函数，即找到

F_k(x)=\sum_{i=0}\begin{Bmatrix}i\\k\end{Bmatrix}x^i

由于第二类斯特林数有递推式，F_k(x) 有性质：

\begin{aligned}F_k(x)&=xF_{k-1}(x)+kxF_k(x)\\&=\frac{x}{1-kx}F_{k-1}(x)\\&=\frac{x^k}{\prod_{i=1}^k(1-ix)}\end{aligned}

这可以分治做，时间复杂度 \mathcal O\!\left(n\log^2n\right)，常数不大。

P5667 拉格朗日插值2

尝试将一般拉格朗日插值的结论运用到本题上。有式子：

f(x)=\sum_{i=1}^ny_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}

也就是说要求

\sum_{i=0}^nf(i)\prod_{j\ne i}\frac{m+k-j}{i-j}

在 k=0,1,\dots,n 时的值。
由于 m>n，所以连乘积中绝对不会有 0 出现，这启示着把连乘积拆开：

\sum_{i=0}^nf(i)\sum_{j\ne i}\frac{\prod_{j\ne i}(m+k-j)}{\prod_{j\ne i}(i-j)}

\begin{aligned}\prod_{j\ne i}(m+k-j)&=\frac{(m+k-n)(m+k-n+1)\cdots(m+k)}{m+k-i}\\&=\frac{(m+k)!}{(m+k-i)(m+k-n-1)!}\end{aligned}

\begin{aligned}\prod_{j\ne i}(i-j)&=\prod_{j<i}(i-j)\prod_{j>i}(i-j)\\&=i!(-1)^{n-i}\prod_{j>i}(j-i)\\&=i!(-1)^{n-i}(n-i)!\end{aligned}

于是上式可写作

\begin{aligned}&\ \ \ \ \ \sum_{i=0}^nf(i)\frac{(m+k)!}{(m+k-i)(m+k-n-1)!i!(-1)^{n-i}(n-i)!}\\&=\frac{(m+k)!}{(m+k-n-1)!}\sum_{i=0}^n\frac{f(i)}{i!(-1)^{n-i}(n-i)!}\frac{1}{m+k-i}\end{aligned}

这样就得到了一个卷积的形式，可以 \mathcal O(n\log n) 计算。对于左侧的系数，可以预处理上升幂。

P5643 [PKUWC2018] 随机游走

“至少经过一次”比较困难，考虑转化。需求到达最后一个点时的期望步数，可以看作 \max。又由于期望的线性性，可以使用 \min-\max 反演：

\mathrm{E}(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}\mathrm{E}(\min(T))

然后就只需要做 \min 了，即对于一个集合 T，求随机游走第一次走到 T 中节点的期望步数。
记 deg_i 为一个点的度数，那么就是要解如下的方程组：

f_i=\begin{cases}0&i\in T\\\frac{1}{deg_i}\sum_{ij\in E} f_j+1&\text{otherwise}\end{cases}

这肯定是可以暴力高斯消元的，但是把 i 的父亲 fa_i 从 i 可以到达的点中分离出来，并将 x 设为根，那么可以找到 f_i 与 f_{fa_i} 的关系（一个一次函数），最后再推回去。

具体地，设目前处理完点 u 的所有孩子 v，找到它们与 u 的关系 f_v=k_vf_u+b_v，需要找到 u 与 fa_u 的关系。那么大力拆式子：

f_u=\frac{1}{deg_u}\left(f_{fa_u}+\sum(k_vf_u+b_v)\right)+1\\deg_uf_u=f_{fa_u}+f_u\sum k_v+\sum b_v+deg_u\\f_u=\frac{1}{deg_u-\sum k_v}f_{fa_u}+\frac{\sum b_v+deg_u}{deg_u-\sum k_v}

这样就求出了 k_u 和 b_u。当 i\in T 时，有 k_i=b_i=0；当 i=x 时，有 f_i=b_i，然后再倒推回去就可以得到每个位置的答案了。但是由于题目中 x 给定，其实不用倒推就已经完成了。
最后对于每个 S 重新枚举 T 不太好，其实可以先高维前缀和求出所有 \mathrm{E}(\max(S)) 的。时间复杂度 \mathcal O\!\left(n2^n\log P\right)，其中 P=998244353。

CF995F Cowmpany Cowmpensation

有一个很好想的 dp，就是设 dp_{i,j} 表示 i 号节点填上 j 的方案数，然而这样是 \mathcal O\left(nd\right) 的。具体式子：

dp_{u,i}=\prod_{u\to v\in E}\sum_{j\le i}dp_{v,j}

初始时有 dp_{u,i}=1。
记 u 子树大小为 siz_u。首先 dp_{u,i} 一定关于 i 是一个多项式；其次考虑加和操作不影响度数，而连乘操作会使度数相加，叶子的度数为 1，那么合并在一起的度数就是 siz_u。因此 dp_{u,i} 关于 i 是一个度数为 siz_u 的多项式，dp_{1,i} 就是一个度数为 n 的多项式。
至此，仅需求出 dp_{1,i}(i\in[1,n]) 的值，然后拉格朗日插值即可得到 dp_{1,d} 的值，时间复杂度 \mathcal O\left(n^2\right)。

P5408 第一类斯特林数·行

第一类斯特林数 \begin{bmatrix}n\\k\end{bmatrix} 指把 n 个物品划分为 k 类，每个类中再做圆排列的方案数。
有递推式：

\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}

但是它没有求单点的快速办法。

到处都有神秘下降幂与上升幂。。

\gdef\ul{\underline}\gdef\ol{\overline}

首先有比较容易的

n^{\underline{a+b}}=n^{\underline{a}}(n-a)^{\underline{b}},n^{\overline{a+b}}=n^{\overline{a}}(n+a)^{\overline{b}}

于是可以像快速幂一样倍增，比如

n^{\ul{2a}}=n^{\ul{a}}(n-a)^{\ul{a}},n^{\ul{2a+1}}=(n-2a)n^{\ul{2a}}

因此，固然可以通过分治在 \mathcal O\!\left(n\log^2 n\right) 的时间复杂度中计算上升幂或是下降幂，但是有一种单 \log 的方法，如果会多项式平移的话。

也在上面的某个链接中更新了。。
然后可以证明这个东西的生成函数刚好就是 x^{\ol{n}}。

Day6

P1587 [NOI2016] 循环之美

如何判断一个既约分数 \frac{p}{q} 是纯循环小数？采取最朴素的判断方式，即设其循环节为 l，满足

\left[\frac{pk^l}{q}\right]=\left[\frac{p}{q}\right]\\\frac{pk^l}{q}-\left\lfloor\frac{pk^l}{q}\right\rfloor=\frac{p}{q}-\left\lfloor\frac{p}{q}\right\rfloor\\pk^l\bmod q=p\bmod q\\k^l\equiv 1\pmod q\\k\perp q

于是要求的变成

\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]\\=\sum_{i=1}^n\sum_{j=1}^m[i\perp j]\sum_{d|j,k}\mu(d)\\=\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[i\perp dj]\\=\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[i\perp j][i\perp d]

至此，设 f(n,m,k) 表示原来要求的答案，那么有递归式：

f(n,m,k)=\sum_{d|k}\mu(d)f\!\left(\left\lfloor\frac{m}{d}\right\rfloor,n,d\right)

边界是当 k=1 时原式变为

\sum_{i=1}^n\sum_{j=1}^m[i\perp j]

这个不难。

不会证时间复杂度。

P4769 [NOI2018] 冒泡排序

首先考虑“好”的排列有什么性质。
打表可知可以用一种增量的方式构造数列，就是放完 [1,i-1] 后要放 i，那么 i 只能插入在一个递增的后缀前面，或者接在末尾。
其实感性理解一下这是对的，因为下界可以得到就是希望移动一个数时别的数不会离自己该在的位置更远。
那这实际上意味着不存在 i<j<k 使得 a_i>a_j>a_k。根据 Dilworth 定理又转化为可以拆成至多两个上升子序列。
先直接做，而不考虑“比 q 的字典序大”的限制。设 dp_{i,j} 表示前 i 个数的最大值为 j 的方案数。那么填大的肯定没错，即 dp_{i,j}\to dp_{i+1,k}(k>j)。如果填小的，那么需要限制住不能出现长度为 3 的下降子序列，这样只能选未选的最小的，这是 dp_{i,j}\to dp_{i+1,j}。
将上面的 dp 用路径的方式呈现，就是始 (0,0)（实际上是 (0,1)，容易发现是一样的）终 (n,n)，不得跨越直线 y=x，只能向上走或向右走的方案数。这是基础的卡特兰数的性质，答案就是 \frac{1}{n+1}\binom{2n}{n}。
回到原问题，采取和数位 dp 类似的手段，卡到字典序大于它的最小的序列，稍微松一下就可以按上面 \mathcal O(1) 地算出（虽然起始点现在不在 (0,0)）。这样的时间复杂度是单次 \mathcal O(n) 的。

P5469 [NOI2019] 机器人

首先可以发现有一个区间 dp，就是设 dp_{[l,r],x} 表示仅考虑 h_{[l\dots r]}，最大值不超过 x 的方案数。那么有仅需要枚举分界点 p，然后答案就是 dp_{[l,p-1],x}\times dp_{[p+1,r],x-1}，如果 x\in[l_p,r_p] 的话。p 的选取和一般的区间 dp 不同，是只有 \mathcal O(1) 个的，因此有用的区间个数其实是不多的。可以先预处理出所有可能达到的区间，设区间数为 m，则时间复杂度自然为 \mathcal O(mV)，可以获得 50pts。
这个值域最终是肯定要去掉的，考虑如何去掉。可以注意到对于固定的 [l,r]，x 可以划分为一些连续段，每个连续段中的转移是本质相同的。把值域离散化下来，那么连续段的总个数是不超过 2n 的，可以每次对一整个连续段进行转移。
对合法区间记一个 id([l,r])，然后预处理一下转移方式，可以看作一张 DAG。
对于每个极短的区间 [L,R]，设 dp_{[l,r],x} 表示最大值不超过 L+x-1 的方案数。可以发现 dp_{[l,r],0},dp_{[l,r],1} 等合在一起是一个 r-l+1 项的多项式，然后拉格朗日插值就可以得到 dp_{[l,r],R-L+1} 了。
这样的时间复杂度是 \mathcal O\!\left(n^2m\right) 的。

Day7

P4128 [SHOI2006] 有色图

先看一些群论。

对于一个群 G，a\in G，记使 a^n=e 成立的最小正整数 n 为 a 的阶，记作 o(a)。若这样的 n 不存在，则称 a 的阶是无限的。
有限群中每一个元素的阶是有限的，但无限群中不一定有无限阶的元素。

定理一：令 S 是 G 的一个非空有限子集，则如下三个命题等价：

证明：2 推 1：首先 aa^{-1}=e\in S，其次 1\cdot a^{-1}=a^{-1}\in S，最后由 b^{-1}\in S 可得 ab=a\left(b^{-1}\right)^{-1}\in S，至此一切群需要的均满足，S\le G。
3 推 1：由于 S 有限，设其中任一个元素为 a，则 a,a^2,a^3,\dots 均在其中，那么 e 也在其中。令 o(a)=n，则取 a^{n-1} 就是 a 的逆元，a^{n-2} 就是 a^2 的逆元，以此类推。故有 S\le G。
1 推 2 和 1 推 3 是定义层面的。至此得证。

定理二：对于一个群 G，若对于元素 a\ne e,a\in G 均有 o(a)=2，则 G 为 Abel 群。
证明：由 a^2=1 知 a=a^{-1}。又因为 \forall a,b\in G,ab\in G 且 (ab)^2=1，有 ab=(ab)^{-1}=b^{-1}a^{-1}=ba，得证。

定理三：对于一个群 G，有 \forall a,b\in G,o(ab)=o(ba)。
证明：令 o(ab)=n,o(ba)=m，由于 (ab)^n=abab\cdots ab=a(ba)^{n-1}b，有 a(ba)^{n-1}b=e。由结合律和消去律知 (ba)^nb=b,(ba)^n=e。因此有 m|n，类似可得 n|m，因此 n=m。

对于一个群 (G,\cdot)，H\le G,a\in G，称 a\cdot H 为 H 的一个左陪集，H\cdot a 为 H 的一个右陪集。

定理四：对于一个非空子群 H\le G，a\in H 与 aH=H 等价。
证明：若 a=e，则显然；否则由于 a\cup H 是一个群当且仅当 a\in H，不然不会有逆元，也是好证的。

定理五：对于一个非空子群 H\le G，a\in G，则有 |aH|=|H|。
证明：由乘法表的性质易得。

定理六：对于一个非空子群 H\le G，a,b\in G，则 b\in aH 与 aH=bH 等价。
证明：由 b\in aH 知存在 c\in H 使得 a\cdot c=b，即 c=a^{-1}b。
令 d\in H，则 ad\in aH。先证明 ad\in bH。这等价于证明 b^{-1}aH\in H。由群的性质知 c^{-1}=b^{-1}a\in H，由群的封闭性知 b^{-1}ad\in H，得证。

定理七：对于一个非空子群 H\le G，a,b\in G，则要么 aH=bH，要么 aH\cap bH=\mathbb\empty。
证明：等价于证明若 aH=bH\ne\mathbb\empty，则 aH=bH。令交集 aH\cap bH 中存在一元素 c，即存在 c\in aH 使得 c\in bH，须证明对于任意 d\in aH 均有 d\in bH。
当 c=a 或 c=b 时，转化为上一个问题证明。否则有 a^{-1}c,b^{-1}c,c^{-1}a,c^{-1}b,a^{-1}d,d^{-1}a\in H，需证 b^{-1}d\in H。则有 b^{-1}d=(b^{-1}c)(c^{-1}a)(a^{-1}d)=b^{-1}(cc^{-1})(aa^{-1})d=b^{-1}d，得证。

定理八：对于一个非空子群 H\le G，ab^{-1}\in H，则 aH=bH。
证明：由于 ab^{-1}\in H，运用定理四得 (ab^{-1})H=H。因此 (ab^{-1}b)H=bH，aH=bH，得证。

定理九：对于一个非空子群 H\le G，有 \bigcup_{a\in G}aH=G。
证明：由 e\in H 可得到。

对于一个非空子群 H\le G，记 [G:H] 表示 |\left\{aH\mid a\in G\right\}|。

拉格朗日定理：对于一个非空子群 H\le G，都有 |H|[G:H]=|G|。
证明：由定理五，定理七和定理九可得。

定义一个有限集合 S=\{a_1,a_2,\dots,a_n\}，其到自身的双射为置换，由如下记号表示：

\begin{pmatrix}a_1&a_2&\cdots&a_n\\a_{p_1}&a_{p_2}&\cdots&a_{p_n}\end{pmatrix}

其中 p_1,p_2,\dots,p_n 是一个排列。

可以证明任意一个置换可以由若干个不交的轮换构成，轮换即

\begin{pmatrix}a_1 &a_2&\cdots&a_{l-1}&a_l\\a_2&a_3&\cdots&a_{l}&a_1\end{pmatrix}

简记为 (a_1,a_2,\dots,a_l)。
证明可以把置换看成 n 个点的有向图，每个点的出度均为 1。
对于一个置换 S，记 c(S) 为它的轮换分解中的轮换个数。

置换的复合是好理解的，这样的二元函数记作 \circ。那么可以证明若所有 n 阶置换的集合为 S_n，则 (S_n,\circ) 是一个群，称其为 n 阶置换群。

对于一个群 G 和一个集合 S，若有二元函数 f:G\times S\to S，满足 \forall a\in S,f(e,a)=a,\forall b 以及 \forall a\in S,b,c\in G,f(b,f(c,a))=f(bc,a)，则称群 G 作用于集合 S。
对于一个被 G 作用的 S，称 a\in S 的轨道为 \left\{f(b,a)\mid b\in G\right\}，记作 G(a)；a 的稳定子为 \left\{b|f(b,a)=a\right\}，记作 G^a。

定理十：对于一个作用于 S 的 G，a\in S，G^a\le G。
证明：直接有 e\in G^a，以及满足结合律（这和元素是什么无关）。
对于 b,c\in G^a，都有 f(b,a)=f(c,a)=a，那么 f(bc,a)=f(b,f(c,a))=a，因此 bc\in G^a，满足封闭性。
对于 b\in G^a，a=f(e,a)=f(b^{-1}b,a)=f(b^{-1},f(b,a))=f(b^{-1},a)，因此 b^{-1}\in G^a，存在逆元。
综上，G^a 是群，又由 G^a\sube G 知 G^a\le G，命题得证。

轨道稳定子定理：对于一个作用于 S 的 G，a\in S，有 |G|=|G(a)||G^a|。
证明：由拉格朗日定理知 |G|=[G:G^a]|G^a|，于是仅需证明 [G:G^a]=|G(a)| 即可。
考虑构造一种一一对应的关系：若 f(b,a)=f(c,a)，则 f(b^{-1}c,a)=f(e,a)=a，那么 b^{-1}c\in G^a。由定理八知 bG^a=cG^a。同理证若 bG^a=cG^a，则 f(b,a)=f(c,a)。
这样就有每个左陪集有且仅有一个 b\in G(a) 与它对应，因此有 [G:G^a]=|G(a)|，得证。

对于一个作用于 S 的集合的置换群 G，若对于 a,b\in S，存在 c\in G 使得 f(c,a)=b，则称 a,b 属于一个等价类。记等价类的集合为 S/G。以及记 S^a=\{b\mid f(a,b)=b\}。
那么对于同一个等价类中的元素，肯定是可以互相等价的。也就是说，对于 T\in S/G,a\in T，均有 G(a)=T。

Burnside 引理：对于一个作用于 S 的 G，|S/G|=\frac{1}{|G|}\sum_{a\in G}\left|S^a\right|。
证明：

\begin{aligned}\frac{1}{|G|}\sum_{a\in G}|S^a|&=\frac{1}{|G|}\sum_{a\in G}\sum_{b\in S}[f(a,b)=b]\\&=\frac{1}{|G|}\sum_{b\in S}\sum_{a\in G}[f(a,b)=b]\\&=\frac{1}{|G|}\sum_{b\in S}\left|G^b\right|\\&=\frac{1}{|G|}\sum_{b\in S}\frac{|G|}{|G(b)|}\\&=\sum_{b\in S}\frac{1}{|G(b)|}\\&=\sum_{T\in S/G}\sum_{b\in T}\frac{1}{|G(b)|}\\&=\sum_{T\in S/G}\sum_{b\in T}\frac{1}{|T|}\\&=|S/G|\end{aligned}

得证。

Pólya 定理专注于染色问题。

Pólya 定理：对于一个作用于 S 上的置换群 G，以及颜色集合 C，则不同染色方案的个数为

\left|C^S/G\right|=\frac{1}{|G|}\sum_{a\in G}|C|^{c(a)}

证明：对于一个 c(a)，其中任一轮换的颜色只能相同，否则不是不动点（严谨地说是否是不动点需要看具体的操作，不过一般的都满足，如“同构”或“旋转后相同”）。因此把 Burnside 引理中的东西替换一下即可。

回到本题。由于 Pólya 定理不能求这么多边的置换，所以只能考虑在点置换的情境下计算边的贡献。
假设现在的一个点置换为 (a_1,a_2,\dots,a_l)(b_1,b_2,\dots,b_m),\dots，对于一条横跨两个置换的边，比如 (a_1,b_1)，那么和它在一个环中的是 (a_2,b_2),(a_3,b_3)，等等。于是环的个数为 \frac{lm}{\operatorname{lcm}(l,m)}=\gcd(l,m)。
对于一条两端点在同一置换中的边，比如 (a_1,a_4)，和它在同一个环中的边都是长度相同的，如 (a_5,a_8)。于是有 \left\lfloor\frac{l}{2}\right\rfloor 个环。
用分拆数枚举点置换之后环长度构成的可重集，然后就不难计算了。时间复杂度可见 OEIS A296010，当 n=53 时大概是 7.7\times 10^7，是可以过的。

P4720 【模板】扩展卢卡斯定理/exLucas

先将 p 质因数分解，假设为 p=p_1^{a_1}p_2^{a_2}\dots p_l^{a_l}，那么变为若干个子问题，每个子问题形如求 \binom{n}{m}\bmod p^k 的值，其中 p 是素数，最终 CRT 在一起即可。
若可求出 n! 一直除去 p 直至不能再整除后的值对 p^k 取模的值，那就做完了。记 n! 中可以除 a 个 p，则问题变为求 \frac{n!}{p^a}\bmod p^k。
将 n! 中所有 p 的倍数提取出来，剩下的构成有小于 p^k 的循环节的东西。例如 n=20,p=3,k=2 时，有：

\begin{aligned}20!&=(3\times 6\times 9\times 12\times 15\times 18)\times(1\times2\times 4\times 5\times 7\times 8)\times(10\times11\times 13\times 14\times 16\times 17)\times(19\times 20)\\&\equiv(3^6\times 6!)\times(1\times 2\times 4\times 5\times 7\times 8)^2\times(19\times 20)\equiv 7\left(\bmod\ 3^2\right)\end{aligned}

真正算时，3^6 一项是不能算的，然后还要递归。最后一段可以直接暴力枚举去算。可以预处理，时间复杂度为 \mathcal O\!\left(p^k+\log n\right)。
至于 a 怎么求，可以仿照上式，仅保留 3^6 一项。

P10594 BZOJ2445 最大团

简记文中的图为 SLC。设 n 个点且节点有标号的 SLC 的个数为 k，则题目要求 m^k\bmod P。转化为求 k\bmod Q 的值，其中 Q=P-1=2\times 13\times 5281\times 7283 是个 square-free 数，可以用 CRT 合并出来。那么现在的问题是求 k\bmod p 的值，但此时 p 可能比较小。
考虑这个 k 到底如何计算。枚举每个极大连通子图的大小 d，则有

k=\sum_{d|n}\frac{1}{\frac{n}{d}!}\binom{n}{d,d,\dots,d}=\sum_{d|n}\frac{n!}{(d!)^{\frac{n}{d}}\frac{n}{d}!}

对阶乘做 exLucas 即可。