NOI 一轮复习 III：数学 A

本文是 NOI 一轮复习的第三篇，包括组合计数、生成函数等数学内容。

组合计数

到处都能见到它的身影，它是一切数数题的基础。

计数基础

概念洪流属于是。

排列数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照一定的顺序排成一列，方案个数记作 $A_{n}^{m}$，有 $A_{n}^{m}=\cfrac{n!}{(n-m)!}$。

一个有限集合 $S$ 到自身的双射称为 $S$ 的一个置换，集合 $S={a_1,\cdots,a_n}$ 的置换可以表示为：

$$f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}$$

是将 $a_i$ 映射为 $a_{p_i}$，这样 $p$ 是 $1\cdots n$ 的一个排列，$S$ 上的所有置换的数量为 $n!$。

置换的过程可以使用有向图来理解，连边 $i\rightarrow p_i$，就是所有点移动 $1$ 的距离。置换中形成一个环的称为置换环，对于大小为 $1,2$ 的置换环，原排列和置换显然是一样的。

对于两个置换 $f,g$ 的乘积记作 $f\circ g$，代表先通过 $f$ 的映射，再通过 $g$ 的映射。

一个排列中的逆序对个数，也叫做反序数，如果是偶数就是偶排列，奇数则是奇排列。

对于一个排列 $1,\cdots,n$，如果将任意两个数 $i,j$ 交换，其它数保持不动，就会得到一个新的排列，那么这样一个变换叫做对换，用 $(i,j)$ 表示。

组合数

从 $n$ 个不同元素中，任取 $m$（$m\leqslant n$）个元素按照任意的顺序组成一个集合，方案个数记作 $\binom n m$。组合数同时也是二项式系数，当 $m<0$ 时，组合数没有定义。

$$\binom n m = \frac{n!}{(n-m)!m!}=\frac {n^{\underline m}} {m!}\\ \binom n m = \binom {n-1} m + \binom {n-1}{m-1}$$

组合数有以下性质 / 恒等式：

1. $\dbinom n m = \dbinom n {n - m}$；
2. $\dbinom{n}{k}=\cfrac{n-k+1}{k}\dbinom{n}{k-1}$，常被用来递推组合数；
3. $\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}$；
4. 吸收恒等式：$\dbinom{r}{k}=\dfrac{r}{k}\dbinom{r-1}{k-1}$，当二项式外有一个无用的系数时，我们可以将它“吸收”进二项式系数。
5. 下指标求和（行求和）：$\displaystyle \sum_{i=0}^{n}\binom{n}{i}=2^n$，相当于是二项式定理中 $a=b=1$。注意这个东西是很特殊的完整一行，一般的行求和是无法快速计算的。它还有变式：
   • $\displaystyle \sum_{i=0}^{n}(-1)^i\binom{n}{i}=0$，这是二项式定理中 $a=1,b=-1$；
   • $\displaystyle \sum_{i=0}^{n}i\times \binom{n}{i}=n2^{n-1}$，因为 $m\times \dbinom{n}{m}=n\times \dbinom{n-1}{m-1}$。
6. 上指标求和（列求和）：$\displaystyle \sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}$，可以看作是枚举第 $m+1$ 个数的位置 $i+1$。
7. 对角线求和：$\displaystyle\sum_{i=0}^{n}\binom{m+i}{i}=\binom{m+n+1}{n}$，反复利用 $C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$ 即可证明。
8. 范德蒙德卷积：$\displaystyle \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$。从组合意义上很容易证明（枚举 $n$ 和 $m$ 中选的个数），常用于合并组合数，考虑它的推论：
   • $\displaystyle \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$，证明很简单，因为 $\dbinom{n}{i-1}=\dbinom{n}{n-i+1},\dbinom{2n}{n-1}=\dbinom{2n}{n+1}$；
   • $\displaystyle\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}$，证明基本同理；
   • $\displaystyle\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}$，这个也是网格图路径计数方案。
9. Lucas 定理。若 $p$ 是质数，则 $\displaystyle\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$，常用于 $p$ 较小的情况。
10. 组合数奇偶性公式。$\displaystyle \binom{n}{m}\equiv 1 \pmod 2 \iff n\ \& \ m=m$，使用 Lucas 定理来证明，需保证不出现 $\dbinom{0}{1}$。
11. Kummer 定理。$\dbinom{n+m}{n}$ 中质因子 $p$ 的次数为 $n+m$ 在计算时 $p$ 进制意义下的进位次数，等价于 $\dbinom n m$ 中质因子 $p$ 的次数等于在计算 $n-m$ 时 $p$ 进制意义下的借位次数。其中 $p$ 是素数。
12. 上指标翻转。$\displaystyle \binom n k = (-1)^k\binom{k-n-1}{k}$。

多重组合数。是指先选 $n_1$，再选 $n_2$，以此类推。有：

$$\binom{n}{n_1,\dots,n_k}=\frac{n!}{\prod_{i=1}^k n_i!}$$

组合方法。在小学学过一些常用的组合方法。

容斥原理

容斥原理是非常重要的计数原理：

$$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|$$

集合的交集可以使用补集容斥原理来求解：

$$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$$

容斥原理最经典的用处是“至少”与“恰好”之间的转化，实际上是一个子集反演的过程。子集反演是针对集合交并的容斥，可以在恰好是某个集合和至多/至少是这个集合反演。

我们先来看与至多是这个集合的反演。现在有其元素满足某种条件的集合 $A$。定义 $f(S)$ 代表 $S=A$ 时的答案，$g(S)$ 代表 $S\subseteq A$ 时的答案。

钦定选了 $S$ 这个集合中的子集 $T$，有 $g(S)=\sum_{T\subseteq S}f(T)$，这时有 $f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)$。使用容斥原理不难感性理解。

类似的，如果 $f(S)$ 代表 $S=A$ 时的答案，$g(S)$ 表示 $A\subseteq S$ 时的答案，有 $g(S)=\sum_{S\subseteq T}f(T)$，反演得 $f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T)$。

这是容斥原理的代数形式，它是我们用容斥原理解决问题的基础。因为在钦定时，一个“有两个元素满足条件”的东西会在“至少有一个元素满足条件”的东西计算时计算两次，也就因此成了一个子集反演的形式。

数数题优先考虑 DP。转移只能对每个点在两棵树上的父亲进行决策，这样 DP 状态只能记录可行的决策点个数，也就是可以作为父亲的点的个数。这样就要钦定剩余节点为叶子节点。

设 $f(S)$ 代表第一棵树的叶子集合恰好为 $S$，$g(T)$ 代表第二棵子树的叶子集合恰好为 $T$。但是我们发现这样还需要考虑“当前是叶子的，当且是叶子而且以后可以变成父亲的”，不好搞！考虑子集反演，设 $f'(S')$ 代表钦定了第一棵树的叶子节点至多为 $S'$，$g'(T')$ 同理，则：

$$\begin{aligned} Ans&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)\\&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}\sum_{S'\subseteq S,T'\subseteq T}f'(S')g'(T')(-1)^{|S|-|S'|+|T|-|T'|} \\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-1)^{n-|S'|-|T'|}2^{n-|S'|-|T'|}\\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-2)^{n-|S'|-|T'|} \end{aligned}$$

相当于钦定了 $S',T'$ 作为可选做父亲的集合（选择一个叶子变成父亲），这样设 $f_{i,j,k}$ 代表考虑到第 $i$ 个节点，$|\{1,\cdots,i\}\cap S'|=j,|\{i+1\cdots n\}\cap T'|=k$ 的方案数。给 $i$ 号点在第一棵子树当中钦定父亲，有 $j$ 中选择父亲的方法；给 $i-1$ 号点在第二棵树中钦定父亲，有 $k$ 种方案，总共 $j\times k$ 种。

$f_{i-1,j,k}$ 可以转移到如下状态：

• $i$ 本来属于 $S'$，可以转移到 $f_{i,j+1,k}$；
• $i$ 本来属于 $T'$，转移到 $f_{i,j,k-1}$；
• 两个都不属于，转移到 $f_{i,j,k}$，容斥系数为 $-2$。

实际上直接猜出容斥系数是更为高效的方式。

初始时 $f_{1,1,k}=1$，统计 $k=1$ 时的答案即可（$S$ 确定 $T$ 自然也确定了）。代码。

---

二项式反演。假设全集 $U=\{S_1, S-2, \cdots, S_{n-1}, S_n\}$，且满足其中任意 $i$ 个集合的并集、交集大小都相等。$g(x)$ 是其中任意 $x$ 个集合的交集的大小，$f(x)$ 是任意 $x$ 个集合的补集的交集的大小。特别地，$g(0)=f(0)=|U|$。

我们有：

$$\begin{aligned} g(n)=\ &|S_1\cap S_2\cap\cdots S_{n-1}\cap S_n|\\ =\ &|U|-|\overline{S_1}\cup\cdots\cup\overline{S_n}|\\ =\ &|U|-\sum_{m=1}^n(-1)^{m-1}\sum_{a_i <a_{i+1}}|\overline{S_{a_1}}\cap\cdots\cap\overline{S_{a_m}}|\\ =\ & |U|-\sum_{i=1}^n(-1)^{i-1}\binom{n}{i}f(i)\\ =\ &\sum_{i=0}^n(-1)^{i}\binom{n}{i}f(i) \end{aligned}$$

$$\begin{aligned} &g(n)=\sum_{i=0}^n(-1)^{i}\binom{n}{i}f(i)\\ \iff& f(n)=\sum_{i=0}^n(-1)^{i}\binom{n}{i}g(i) \end{aligned}$$

如果令 $f(i)'=(-1)^i f(i)$，那么可以得到另一个形式（这个形式更为常用，因为大多数题并不会凑出一个 $-1$，以下式子中的 $f,g$ 均没有特定的含义）：

$$\begin{aligned} &g(n)=\sum_{i=0}^n\binom{n}{i}f(i)\\ \iff& f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i) \end{aligned}$$

同时还有一种上指标的二项式反演：

$$\begin{aligned} &g(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}f(i)\\ \iff& f(n)=\sum_{i=n}^N(-1)^i\binom{i}{n}g(i) \end{aligned}$$

$$\begin{aligned} &g(n)=\sum_{i=n}^N\binom{i}{n}f(i)\\ \iff& f(n)=\sum_{i=n}^N(-1)^{i-n}\binom{i}{n}g(i) \end{aligned}$$

Prufer 序列

Prufer 序列的构建过程并不重要，重要的是它的性质。

Prufer 序列可以将一个 $n$ 个节点的无根树用 $[1,n]$ 中的 $n-2$ 个整数表示，那么完全图有 $n^{n-2}$ 棵生成树，因为每一个 Prufer 序列都对应一棵树。这就是 Cayley 公式。

一个数在 Prufer 序列中出现的次数是它在原树中的度数减一。

格路计数

在格点路径上，$(0,0)\rightarrow (n,m)$ 的方案数是 $\dbinom{n+m}{n}$。

对于不能经过某一条直线的限制，可以采用反射容斥。发现它们反射之后都会到达同一个点：

[JLOI2015] 骗我呢。写出暴力 DP 转移方程后发现这其实是个格路计数问题，起点是 $(0,0)$，终点是 $(n+m+1,n)$，不能碰到 $y=x+1, y=x-m-2$。

我们将终点 $T$ 做关于两条直线的对称，得到 $T1,T2$（翻转之后的路径也是可以翻转的）。这样我们只需要减去经过两条直线的方案数，而且是最后经过的（否则先经过一条直线再经过另一条的这种会算重，要及时减去）。

解题思路

计数题有一些机械化思考的方式，这里介绍一些：

寻找唯一性

组合计数中最常见的问题是“数重”和“数漏”。解决方式一般只有两种：

• 构造双射，把合法元素唯一对应到一种合法方案上，相当于添加了限制条件；
• 重的方案可以使用容斥原理解决，等价方案可以使用 Polya 定理解决。

由于方案不同仅当颜色不同，因此我们从球的颜色角度考虑去计数。

有 $R$ 个红球，$B$ 个蓝球，那么 $R\ge B+n$ 时必定有解，否则有解满足 $B\le R<B+n$。此时让 $R-B$ 只龙红球吃的比蓝球多一个，$n-(R-B)$ 只龙吃的红球和蓝球一样多，但最后一个吃了个蓝球。

$R=B$ 的情况等价于 $(R,B-1)$。

我们强制要求蓝红吃的一样多的龙吃的序列形如 RBRBRBRB，否则我们可以将其中不满足的拉出来，喂给多吃了红色球的龙吃。

现在要求在序列中可以提取出至少 $n-(R-B)$ 个 RB 子序列。可以看作横着的格路计数，不能越过 $y=-(n-R)$。代码。

例题

某些东西的难度可能比较大。

[ABC160F] Distributing Integers

Portal.

非常经典。发现只需要满足子树中根节点是第一个出现的，因此对于一个子树将答案除掉 $sz$，换根 DP 即可。代码。

[CF1762E] Tree Sum

Portal.

设连接 $i$ 的边权为 $d_i$，而每条边对 $\prod d_i$ 的贡献为 $1$，然而 $n$ 为奇数时 $\prod d_i=-1$ 永远不可能满足，因此 $n$ 为奇数时无解。

如果 $n$ 为偶数且树的形态固定，那么参考 Prufer 序列的构造方式，从叶子开始赋予边权，那么方式一定是唯一的！也就是说，对于给定的树的形态只有一种方式。

这样的话，一条边 $(u,v)$ 的权值为 $1$ 的充要条件是：断掉这条边之后两个连通块大小均为偶数。因为这样两个连通块都满足条件了，这条边填 $1$ 即可。

考虑逐边计算贡献，枚举 $1$ 所在的连通块大小 $i$，这样 $n$ 所对应的连通块大小便为 $n-i$。

• 此时这条边的边权为 $(-1)^i$。
• 剩下 $n$ 个点中随便扔，方案数为 $\binom{n-2}{i-1}$。
• 两块随便制造无根树，根据 Cayley 公式计算即可。
• 随便找两个点连接。

代码。

[AGC002F] Leftmost Ball

Portal.

考虑最终形成的合法序列，一定是 $k$ 个白色球加上 $n$ 中颜色的球各 $k-1$ 个，合法情况是前缀白球个数大于等于其它颜色数。

$f_{i,j}$ 表示 $i$ 个白球，放了 $j$ 个颜色的方案数。

决策有两种：

• 放置一个白球，有 $f_{i,j}\stackrel{+}{\leftarrow} f_{i-1,j}$；
• 加入新颜色的球，即从 $f_{i,j-1}$ 转移。系数是多少？首先需要在 $n-j+1$ 中选择一个作为这时放置的颜色，将其中一个放置在第一个空位，然后剩下的 $k-2$ 个在后面的 $nk-i-(j-1)(k-1)-1$ 中找 $k-2$ 个放即可。

然后就完了。代码。

* [LNOI2022] 盒

Portal.

真·组合数基础练习题！

发现 $w_i$ 会被使用 $\sum |\sum_{j=1}^i b_j-\sum_{j=1}^i a_j|$ 次。枚举 $j=\sum_{k=1}^i b_k$，将 $a$ 转化为其前缀和，合法的 $i,j$ 的出现条件是前 $i$ 个数和为 $j$，后 $n-i$ 个数和为 $S-j$，于是直接插板可以得到总贡献：

$$\sum_{i=1}^{n-1}w_i\sum_{j=0}^S |j-a_i|\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}$$

这样的时间复杂度是 $O(nS)$ 的。考虑拆绝对值，大概像这样：

$$\sum_{i=1}^{n-1}w_i\sum_{j=0}^S (j-a_i)\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}+2\sum_{i=1}^{n-1}w_i\sum_{j=0}^{a_i} (a_i-j)\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}$$

这样让 $j$ 从 $0$ 开始枚举的目的是让接下来好算。后面的式子显然条件更强，因此以后面那个为例。由于出现减法不好搞，因此拆掉：

$$\sum_{j=0}^{a_i} a_i \binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}-\sum_{j=0}^{a_i} j\binom{j+i-1}{i-1}\binom{S-j+n-i-1}{n-i-1}$$

前面那个 $a_i$ 可以直接搞出来，后面那个利用 $\binom{n}{m}=\binom{n}{m-1}(n-m+1)$ 将 $j$ 改为 $i$ 再扔出来。

现在仅剩的问题就是快速计算：

$$f(n,m,i,k)=\sum_{j=0}^k \binom{j+i-1}{i-1}\binom{m-j-1+n-i}{n-i-1}$$

快速计算 $f(n,m,i,k)$？然而这个式子是拆不动了，考虑使用增量法计算。$k$ 的增量是好处理的，但是 $i$ 呢？不知道。从组合意义的角度考虑，$f$ 是将前 $i$ 个和 $\le k$ 的数，且所有 $n$ 个数和为 $m$ 的方案数。相当于是将 $m$ 个相同的球放到 $n$ 个不同的盒子中，前 $i$ 个盒子最多只能放 $k$ 个球，相当于第 $k+1$ 个小球不在前 $i$ 个盒子里！那么枚举放的位置，插板有：

$$f(n,m,i,k)=\sum_{j=i+1}^n \binom{k+j-1}{j-1}\binom{m-k-1+n-j}{n-j}$$

那么就可以使用这个式子维护 $i$ 的增量了。代码。

[CF985G] Team Players

Portal.

一眼看去在补图上跑三元环计数，然后发现边数爆炸，直接告辞。

但是唯一会的好像就是数三元环。考虑求答案的补集，答案应该是所有三元组的答案，减去至少有一条边的三元组的答案。

然后后面这个怎么做呢？我们肯定是要去看边的，这样就会导致对于一个有两条边的三元组，被统计两次。因此后面这个也需要容斥。

最终答案就是所有三元组的答案（1），减去至少有一条边的答案（2），加上至少有两条边的答案（3），减去有三条边的答案（4）。接下来分别看这四个东西怎么做。

1. 枚举 $u\in [0,n)$ 中在三元组 $(i,j,k)$ 的位置，然后利用乘法原理计算答案。

2. 只有一条边，那么枚举所有边 $(x,y)$，不妨令 $x<y$，然后令第三个点为 $z$，考虑 $x,y,z$ 对三元组 $(i,j,k)$ 的贡献。

   • $x=i$，此时 $z>x$，$x$ 的贡献为 $A\times x\times (n-x-2)$；
   • $x=j$，此时 $z<x$，$x$ 的贡献为 $B\times x\times x$；
   • $y=j$，此时 $z>y$，$y$ 的贡献为 $B\times y\times (n-y-1)$；
   • $y=k$，此时 $z<y$，$y$ 的贡献为 $C\times y\times (y-1)$；
   • $z=i$，此时 $0\le z<x$，$z$ 的贡献为 $\displaystyle A\times \sum_{p=0}^{x-1}p=A\times \frac {x\times (x-1)} 2$；
   • $z=j$，此时 $x<z<y$，$z$ 的贡献为 $\displaystyle B\times \sum_{p=x+1}^{y-1}p=B\times\frac{(x+y) \times (y-x-1)} 2$；
   • $z=k$，此时 $y<z<n$，$z$ 的贡献为 $\displaystyle C\times \sum_{p=y+1}^{n-1}p=C\times \frac{(n+y)\times (n-y-1)} 2$。

3. 两条边，要求的是三个点的链。不妨考虑枚举的是中间点 $x$，此时 $x=j$。枚举 $x$ 的每一条出边到达点 $y$，设 $x$ 的出度为 $t$。由于 $x$ 也会影响 $y$ 充当的是 $i,j$ 还是 $k$，因此不妨把 $x$ 也加进 $x$ 的出边中（$t$ 同时也增大 $1$）。设 $y$ 在这些数中的排名为 $r$，分两种情况计算 $y$ 的贡献：

   • $y<x$，此时考虑第三个点 $z$ ：
     • $z>y$，$y$ 的贡献为 $A\times y\times (t-r-2)$；
     • $z<y$，$y$ 的贡献为 $B\times y\times r$；
   • $y>x$，此时考虑第三个点 $z$；
     • $z>y$，$y$ 的贡献为 $B\times y\times (t-r-1)$；
     • $z<y$，$y$ 的贡献为 $C\times y\times (r-1)$。

   然后对于 $x$ 自己要进行一个统计，考虑三种情况：

   • $y,z<x$，$x$ 的贡献为 $C\times x\times \dfrac{r\times (r-1)}{2}$；
   • $y,z>x$，$x$ 的贡献为 $A\times x\times \dfrac{(t-r-1)\times (t-r-2)}{2}$；
   • $y<x,z>x$，$x$ 的贡献为 $B\times x\times r\times (t-r-1)$。

4. 直接搞一个三元环计数模板就行。

于是就很高兴地做完了，时间复杂度应该是 $O(n)+O(m)+O(n+m)+O(m\sqrt{m})=O(n+m\sqrt{m})$。代码。

Polya 计数理论

容斥原理可以防止算重，而想要知道问题有多少个互不等价的解，可以使用 Polya 定理。

群论概述

群是由一种集合 $G$ 以及一个二元运算所组成的，它的二元运算用 $a\cdot b$ 表示，要求满足群公理：

• 封闭性，$\forall a,b\in G, a\cdot b\in G$。
• 结合律，对于 $G$ 中的任意元素，其二元运算需要满足结合律。
• 单位元，$G$ 中存在一个元素 $e$，使得对于 $G$ 中的任意一个元素 $a$，都有一个 $e\cdot a=a\cdot e=a$ 成立。这个元素应该是唯一的，被称为群的单位元 $e$。
• 逆元，对于 $G$ 中的 $a$，总存在 $G$ 中的一个 $b$ 满足 $a\cdot b=b\cdot a=e$，称 $b$ 为 $a$ 的逆元，记为 $a^{-1}$。任何一个元素的逆元是唯一的。

这样，$(G,\cdot)$ 被称为一个群。例如，$(\mathbb{Z},+)$ 是一个群，$e=0$，一个数的逆元是它的相反数。

如果 $(G,\cdot)$ 满足封闭性和结合律，那么它就是一个半群；如果还满足单位元，那么它就是幺半群；如果群 $(G,\cdot)$ 满足交换律，即 $\forall a,b\in G, a\cdot b=b\cdot a$，那么这是一个阿贝尔群，又称交换群。

若 $H\subseteq G$，且 $(H,\cdot)$ 是群，那么 $(H,\cdot)$ 是 $(G,\cdot)$ 的一个子群。可以记作 $H\le G$。

定义 $gH=\{g\cdot h|h\in H\}$ 为 $H$ 关于 $g$ 的左陪集，$Hg=\{h\cdot g|h\in H\}$ 为 $H$ 关于 $g$ 的右陪集，其中满足 $g\in G$。

如果 $Hg_1\cap Hg_2\ne \varnothing$，那么 $Hg_1=Hg_2$。这一点不难感性理解。另外，$|H|=|Hg|$，因为 $gh_i$ 必然互不相同。

拉格朗日定理：$H$ 关于 $G$ 中元素的陪集有 $\frac{|G|}{|H|}$ 种，两两不交且大小均为 $H$。陪集的种类数可以记作 $[G:H]$。

置换群

置换群 $G=(M,\cdot)$，其中 $M$ 是置换的集合，运算是置换的合并运算。

Burnside 引理

定义置换群 $G$，其作用于 $X$，如果 $x,y\in X$ 在 $G$ 的作用下可以相等，也就是说，存在 $g\in G$ 使得 $g(x)=y$，那么 $x,y$ 是等价的。可以得到不同等价类的数量：

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}X^g$$

$X^g$ 指 $X$ 在 $g$ 作用下的不动点的数量，即满足 $g(x)=x$ 的 $x$ 的数量。

Polya 定理

在本题中，置换群 $G$ 可以看作旋转 $0\sim n-1$ 个点的集合。我们得到：

$$Ans=\frac{1}{|G|}\sum_{g\in G}X^g$$

我们依次考虑每个置换对于答案的贡献，旋转 $0$ 个的答案是 $n^n$，剩下的呢？

旋转 $k$ 个时，一个元素是不动点，当且仅当在颜色序列中，存在一个长度为 $a$ 的循环节满足 $a\mid \gcd(n,k)$。那么，每个子串的前 $\gcd(n,k)$ 个都是随便取的，所以最终答案为：

$$\frac 1 n \sum_{k=1}^{n}n^{\gcd(n,k)}$$

欧拉反演即可，也就是：

$$\frac 1 n \sum_{d\mid n}n^d\times \sum_{k=1}^{n} \left[\gcd\left(n,k\right)=d\right]$$

欧拉函数可以直接计算，代码。

说了半天，Polya 定理是什么呢？我们要知道不动点的数量，实际上就是置换环的个数！因为置换环内的点应该是相同的颜色，否则换一换就重了。那么可以写出（$c$ 代表 $g$ 中置换环的个数）：

$$\frac{1}{|G|}\sum_{g\in G}n^{c(g)}$$

例题

理论上来讲不太常见。

[CF1065E] Side Transmutations

Portal.

一个操作只有用和不用两种情况，将 $b$ 数组差分之后每一段是独立的，然后可以写出：

$$\frac {1}{2^m}\sum_{C} t^{n-\sum C}$$

这东西拆掉就能做了。代码。

[ARC062D] Painting Graphs with AtCoDeer

Portal.

如果不是点双上的边，那随便填；如果是只有一个环的点双上的边，那么 Polya 定理模板；如果是其它，那么插板即可。代码。

[SHOI2006] 有色图

Portal。

置换依然考虑点的置换，但是这次染色的是边。我们要知道边有多少个等价类。

考虑找到所有的置换环，设其大小为 $c_i$，然后讨论等价类：

• 两个环内点：我们只关心两点在环上的距离，可以进行染色的不动点数量是 $c_i/2$；
• 一个环内，一个环外点：可染色的不动点数量是 $\gcd(c_i,c_j)$。

枚举 $n$ 的拆分即可。注意当中不能算重，在所有点全排列的基础上（然后向置换里面填），原本的同样大小的置换环要除以其全排列，置换环内的点没有顺序。代码。

概率论

题车

此部分介绍的内容可能是目前算法竞赛中最常出现的内容，因此题非常多。

刷基础 1

简单计数。

[COCI2009-2010#6] XOR

Portal.

不难看出是容斥，但是系数是什么？手玩之后发现是 $2^{s-1}$，其中 $s$ 是三角形的个数。代码。

[CF1227F] Wrong Answer on test 233

Portal.

其中一个答对的更多，都可以 swap 一下变成另一个答对的更多，因此考虑容斥求出两者答对的一样多的方案数。

先排除掉相邻 $h_i$ 相等的情况，因为这样必定都对，随便填都行。

枚举答对的数量，由于一个是对的位移的就不可能是对的，因此先后选择两次答对的数，然后强制钦定剩下的都不对。代码。

[CF1503E] 2-Coloring

Portal.

考虑什么样的染色方式是符合要求的。要么蓝色贯穿，要么不贯穿。

钦定左边蓝色的高度和两个蓝色峰值的位置，枚举最右面的峰值，然后高度要求和是 $n$。

这个翻转之后是一样的，注意第二次计算时要强制钦定 $i-j\ge 2$，防止出现两个都是峰的情况。前缀和优化即可。代码。

* [JLOI2016] 成绩比较

Portal.

首先在 $n-1$ 名同学中钦定 $k$ 名同学被 B 神碾压。

需要钦定同学分数的具体情况，此时对于每一科可以分开考虑。

考虑 $G(u,a,b)$ 代表有 $u$ 种可选分数，$a$ 人比 B 神高，$b$ 人不比 B 神高，则：

$$G(u,a,b)=\sum_{i=0}^u i^a (u-i)^b$$

直接做会爆炸，考虑枚举有 $t$ 种得分，答案为 $d(t)$，根据容斥原理得：

$$d(t)=\binom{u}{t}\left(G(t,a,b)-\sum_{i=1}^{t-1}d(i)\times \binom{t}{i}\right)$$

然后需要分配这些分数给每一个人，这里考虑分配给不被 B 神碾压的比较方便，在 $n-1-k$ 个同学中，让 $r_i-1$ 个人第 $i$ 科分数比 B 君高，方案数为 $\dbinom{n-k-1}{r_i-1}$。但是不对！我们需要保证这些人都不能被 B 君碾压！设 $f_i$ 代表不超过 $i$ 个人被碾压的方案数，那么：

$$f_i=\prod_{j=1}^{m} \binom{n-i-1}{r_j-1}$$

容斥原理，得到答案：

$$\sum_{i=0}^{n-k-1}(-1)^{n-k-1-i} f_i\binom{n-k-1}i$$

将三个东西全部乘起来即可，代码。

刷基础 2

含有概率和期望的问题。

[CF850F] Rainbow Balls

Portal.

设 $f(x)$ 代表钦定一个当前有 $x$ 个球的颜色，将全部 $s$ 个球转化成这个颜色的期望操作次数。根据期望的线性性质，最终答案是 $\sum f(a_i)$。

如果转移到 $f(0)$ 就完蛋了。

直觉上来讲是这样的：

$$p=\frac{x(s-x)}{s(s-1)}\\ f_x=p(f_{x-1}+f_{x+1})+(1-2p)f_x + 1$$

直接转移到了 $f(0)$ 怎么办？不，贡献不能是 $1$，它想要走到 $s$ 一定不能中途暴毙，所以贡献是 $\cfrac i s$。

知道 $f_1$ 是多少，一切就解决了。我们还知道 $f_s=0$，那么：$f_1=f_1-f_s=\sum_{i=2}^s f_i-f_{i-1}$，代入即可得到 $f_1=\cfrac{(s-1)^2}{s}$。代码。

[Ptz 2019 Summer Day 3] Minimum Spanning Trees

Portal.

设 $f_{i,j}$ 代表 $i$ 个点的树 MST 为 $j$ 的答案。转移时用 $g_{i,j}$ 代表形成大小和为 $i$ 的连通块，MST 为 $j$ 的答案。此时的 MST 连接各连通块的边用当前枚举的边权定义。之后再把当前不连通的减去即可。代码。

刷提升

经典套路的综合应用。真的是非常有趣呢

* [ARC128F] Game against Robot

Portal.

首先给定 $p$ 怎么做？每次将后两个数丢进大根堆里，选择最大的即可。也就是说，我们只需要维护第 $i$ 大的数出现的次数 $f_i$。

然后还是有值的限制，不好做，继续降维，将 $f_i$ 改为求前 $i$ 大的数被统计的次数，那么答案是 $\sum a_i\times (f_i-f_{i-1})$。这样就考虑 01 序列的形态即可。

每两位一组，一个 $1$ 横着走（方案数为 $2$），右上走和右下走方案数为 $1$，走到 $(n,m)$。怎么做！打表，是 $\dbinom{2n}{n+m}$。

现在求的是这个东西：

但是我们要求这个：

枚举红线的个数（触发大根堆里找不到 1 的次数）$k$，那么最终要走到 $(n/2,m-n/2)$，恰好要经过最低点 $y=-k$，反射容斥再差分，答案是：

$$\dbinom{n}{m+2k} - \dbinom{n}{m+2k+2}$$

然后枚举 $k\in [\max\{0,n/2-m\},n/2]$，令 $p=\max\{0,n/2-m\}$，统计答案：

$$\begin{aligned} \frac{f_m}{m!(n-m)!}&=\sum_{k=p}^{n/2}\left(\frac n 2-k\right) \left( \dbinom{n}{m+2k} - \dbinom{n}{m+2k+2}\right)\\ &=\frac n 2 \sum_{k=p}^{n/2} \left( \dbinom{n}{m+2k} - \dbinom{n}{m+2k+2}\right)-\sum_{k=p}^{n/2}k \left( \dbinom{n}{m+2k} - \dbinom{n}{m+2k+2}\right)\\ &=\frac n 2 \sum_{k=p}^{n/2} \left( \dbinom{n}{m+2k} - \dbinom{n}{m+2(k+1)}\right)-\sum_{k=p}^{n/2}k \dbinom{n}{m+2k} + \sum_{k=p+1}^{n/2+1}(k-1)\dbinom{n}{m+2k}\\ &=\frac n 2 \dbinom{n}{m+2p} -p\binom{n}{m+2p} - \sum_{k=p+1}^{n/2} \dbinom{n}{m+2k} \end{aligned}$$

就完成了。代码。

[AGC043D] Merge Triplets

Portal.

考虑按照数从小到大进行 DP。发现前缀最大值段的长度 $\le 3$，然后长度为 $2$ 的段个数不超过长度为 $1$ 的段个数。代码。

[ARC082C] ConvexScore

Portal.

贡献是合法点集的数量，其中合法的定义是它们中可以选出一些点构成一个凸多边形围住所有的点。因此直接统计所有的线段即可。代码。

[CTS2019] 随机立方体

Portal.

首先把恰好二项式反演掉。然后我们需要计算至少 $i$ 个极大点出现的概率。

钦定 $i$ 个极大点的方案数是 $\displaystyle A_{n}^{i} A_{m}^i A_l^i\times \prod_{j=1}^i \cfrac{1}{nml-(n-j)(m-j)(l-j)}$。后面这个东西可以理解为钦定每个点比它要比的东西都大的概率，因为前面强制钦定了 $i$ 个关键点的顺序。代码。

刷综合

综合计数题。

[AGC040F] Two Pieces

Portal.

代数推导天地灭。

考虑没有 $2$ 操作怎么做。为了避免重复计数，强制让 $a,b$ 距离 $\ge 1$（我们只区分操作时的位置，因此 $=0$ 的会在考虑 $2$ 操作时统计）。反射容斥做一下即可。

考虑加入操作 $2$。考虑枚举一次操作 $2$ 造成的移点贡献，也就是枚举最后一次进行操作 $2$ 时的 $k=x-y$，那么可以视作将终点拉到 $(A,B-k)$，将此视为新的格路。

将剩余的 $n-A-(B-k)-1$ 个 $3$ 操作分配到操作序列中，实际上是要给到 $k+1$ 个点（在它们身上进行 $3$ 操作），它们是直线 $y=x-d$（$d\in [0,k]$，$d>k$ 越过了之前钦定的最后一次 $3$ 操作）与新的格路的最后一个交点，只有最后一个交点是合法的，否则会有将 $y$ 坐标 +1 类的操作无法进行。分配之后，会将移动 $k$ 的贡献分摊掉。

特判 $A+B=n$ 的情况即可。代码。