本部分为 线性代数 / 反演 / 概率期望 / 群论 / 博弈论 笔记。

行列式求值

  • 行列式：是矩阵得到的一个标量（数值）。我们记矩阵 $A$ 的行列式为 $\det(A)$，它的定义为

$$\det(A)=\sum_p (-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}$$

其中 $p$ 是一个排列，$\tau(p)$ 为排列 $p$ 的逆序对个数。行列式的求值过程相当于用排列的逆序对作为容斥。

行列式与矩阵变换的关系：

  • 交换矩阵的两行/列，行列式变为相反数；
  • 将矩阵的一行整体乘一个常数 $k$，行列式也乘以 $k$；
  • 将矩阵的一行加到另一行上，行列式不变。

行列式(快速)求值：注意到以上三条性质类似于高斯消元的前置条件。我们可以利用高斯消元的思想(步骤)，将行列式对应的矩阵消元为只有斜向右上区域存在数值的矩阵。此时，我们可以发现此时的行列式 $\det(A)=\prod\limits_{i=1}^n a_{i,i}$。注意消元时乘上 $(-1)^\text{交换次数}$ 即可。

时间复杂度 $O(n^3)$。

注意如果模数不是质数，我们可以选择使用辗转相除法来解决。使用辗转相除法的时间复杂度要多一个 $\log p$。

LGV 引理

给出一个 $n·n$ 的网格图，其中 $(x,y)$ 只能走到 $(x+1,y)$ 或 $(x,y+1)$。给定 $m$ 对点 $A_i(1,a_i)$ 和 $B_i(n,b_i)$。求让 $A_i$ 走到 $B_i$ 且路径不相交的方案数。

保证 $\forall i\in[1,n),a_i\le a_{i+1},b_i\le b_{i+1}$，并且 $\forall i\in[1,n],a_i\le b_i$。

考虑容斥，我们枚举排列 $p$，钦定 $A_i$ 最终走到了 $B_{p_i}$。那么方案数为 $\prod\limits_{i=1}^n \dbinom{b_{p_i}-a_{i}+n-1}{n-1}$。容斥系数为 $(-1)^{\tau(p)}$，它的组合意义是，以出现了多少个路径的交点（逆序对个数）来容斥。

不妨设 $A_i$ 走到 $B_j$ 的方案数为 $w(i,j)=\dbinom{b_j-a_i+n-1}{n-1}$。因此答案为 $\sum\limits_{p}(-1)^{\tau(p)}\prod\limits_{i=1}^n w(i,p_i)$。

我们发现这个式子和行列式定义式是同一种形式。因此，我们直接求矩阵 $w$ 的行列式即为答案。

事实上 LGV 引理不仅仅限于网格图行走数数题，它的使用条件（参考 讨论区）：

  • 在 DAG 上走路，求若干对点不相交路径的方案数。
  • 任何一种 不相交 路径方案对应的排列均为 $[1,2,\dots,n]$。
  • 可以快速算出一个点到另一个点的行走路径方案数。
  • 或者计算「偶数个交点个数与奇数个交点个数方案数之差」的一般 DAG 问题也可以使用 LGV 引理。

矩阵树定理

矩阵树定理用于求无向图的生成树数量，或者有向图指定根外向/内向生成树数量。

无向图生成树计数

  • 度数矩阵 $D$：对于一个无向图，我们定义 $D_{i,i}$ 为点 $i$ 的度数，而其他的 $D_{i,j}=0(i\ne j)$；
  • 邻接矩阵 $G$：对于一个无向图，我们定义 $D_{i,i}=0$，而其他的 $D_{i,j}(i\ne j)$ 为点 $i$ 与点 $j$ 之间所连的边数。由定义有 $G_{i,j}=G_{j,i}$；
  • Laplace 矩阵（亦称 Kirchhoff 矩阵） $L$：对于一个无向图，$L=D-G$。
  • 主子式：在 $n$ 阶（$n$ 行 $n$ 列）的行列式中，我们选取若干行（如第 $1,2,5$ 行），再选取与行号相同的列号（第 $1,2,5$ 列），将由上述选取的行列交汇处的元素所组成的新的行列式称为「$n$ 阶行列式的一个 $i$ 阶主子式」。

无向图生成树个数等于 $L$ 的任意一个 $(n-1)$ 阶主子式的行列式的值。即我们将 $L$ 的 任意 第 $i$ 行&列去掉后的行列式。

有向图生成树计数

我们对 Laplace 矩阵的定义做一些更改：

  • 出度数矩阵 $D^{out}$：对于一个有向图，我们定义 $D_{i,i}$ 为点 $i$ 的出度数，而其他的 $D_{i,j}=0(i\ne j)$；类似地定义入度数矩阵 $D^{in}$。
  • 邻接矩阵 $G$：对于一个有向图，我们定义 $D_{i,i}=0$，而其他的 $D_{i,j}(i\ne j)$ 为点 $i\to j$ 的边数。
  • 出度 Laplace 矩阵 $L^{out}=D^{out}-G$。
  • 入度 Laplace 矩阵 $L^{in}=D^{in}-G$。

我们记规定的根为 $r$，

  • 根向树（即内向树，指向根的生成树）的个数为，将 $L^{out}$ 的第 $r$ 行&列去掉后得到的主子式的行列式的值。
  • 叶向树（即外向树，指向叶子的生成树）的个数为，将 $L^{in}$ 的第 $r$ 行&列去掉后得到的主子式的行列式的值。

注意：内向树用的是出度，外向树用的是入度。为避免混淆可以用根向树叶向树来记忆。

前面无向图可以将任意同一行&列去掉的原因是，我们可以指定一个点作为无向图的根。

如果没有指定根，我们应依次将第 $i$ 行&列去掉的主子式的行列式的值的 总和。

带权生成树边权积之和

注意到矩阵树定理可以允许重边存在，因此我们可以将边权视作「重边个数」。然后就可以转化为上述问题了。

此时，度数矩阵 $D_{i,i}$ 为点 $i$ 所连边权之和；邻接矩阵 $G_{i,j}$ 为两点所连边权之和。

换句话说，Laplace 矩阵的主子式的行列式求的是 $\sum\limits_{T}\prod\limits_{(u,v)\in T}w(u,v)$，我们的任务就是精心构造 $w(u,v)$ 即可，其他的我们动不了。

带权生成树边权和之和

我们考虑计算每一条边的贡献，即 $w_i\times\text{出现次数}$，因此考虑利用卷积思想，将边修改为 $w_{i}·x+1$，定义两个一次式的乘积需要 $\bmod x^2$。

然后还是按照上述方法构造矩阵求行列式。最后行列式的值的一次项系数即为答案。

带权生成树 $k$ 次幂之和

一颗生成树 $\mathrm T$ 的贡献为 $\left(\sum\limits_{(u,v)\in\mathrm T}w(u,v)\right)^k$，即在生成树里面任意挑 $k$ 条边求乘积再加起来，这种组合意义类似于二项卷积。因此我们考虑将边权构造为指数生成函数 $\sum\limits_{i=0}^k w^i·\dfrac{x^i}{i!}$，那么最后求出来的行列式的值的 $k$ 次方系数再乘上 $k!$ 即为答案。

需要计算多项式的逆，并且时刻对 $x^{k+1}$ 取模。

二项式反演

恰好与至多的转化

设 $f_i$ 为选择恰好 $i$ 个元素的方案数，$g_i$ 为钦定 $i$ 个元素不作限制，其他元素必须不能满足的方案数，则有 $g_n=\sum\limits_{i=0}^n\dbinom{n}{i}f_i$.

根据二项式反演有 $f_n=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}g_i$.

证明：

$$\begin{aligned} f_n&=\sum_{i=0}^n(-1)^{n-i}\dbinom{n}{i}\sum_{j=0}^i\dbinom{i}{j}f_i\\ &=\sum_{i=0}^nf_i\sum_{j=i}^n(-1)^{n-j}\dbinom{n}{j}\dbinom{j}{i}\\ &=\sum_{i=0}^nf_i\sum_{j=i}^n(-1)^{n-j}\dbinom{n}{i}\dbinom{n-i}{j-i}\\ &=\sum_{i=0}^nf_i\dbinom{n}{i}\sum_{j=i}^n(-1)^{n-j}\dbinom{n-i}{j-i} \end{aligned}$$

由于我们知道 $\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}=[n=0]$，因此在上面只有当 $i=n$ 的时候 $f_i$ 的系数为 $\dbinom{n}{n}\times1=1$，其他的系数均为 $0$。这样我们就成功证明了二项式反演公式。

$\triangle$ 恰好与至少的转化

设 $f_i$ 为选择恰好 $i$ 个元素的方案数，$g_i$ 为钦定选择 $i$ 个性质，其他性质不作限制的方案数，那么有 $g_k=\sum\limits_{i=k}^n\dbinom{i}{k}f_i$.

根据二项式反演有 $f_k=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}g_i$.

证明：

$$\begin{aligned} f_n&=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}\sum_{j=i}^n\binom{j}{i}f_j\\ &=\sum_{i=k}^nf_i\sum_{j=k}^i(-1)^{i-j}\binom{i}{j}\binom{j}{k}\\ &=\sum_{i=k}^nf_i\sum_{j=k}^i(-1)^{i-j}\binom{i}{k}\binom{i-k}{j-k}\\ &=\sum_{i=k}^nf_i\binom{i}{k}\sum_{j=k}^i(-1)^{i-j}\binom{i-k}{j-k}\\ \end{aligned}$$

我们同样可以通过讨论 $f_i$ 的系数得到一样的结论。

我们可以通过分离系数的方式用 $\texttt{FFT/NTT}$ 加速在 $O(n\log n)$ 时间内进行二项式反演。

Min-Max 容斥

记 $S$ 为一个集合，$\max(S)$ 为该集合内元素的最大值，$\min(S)$ 为该集合内元素的最小值。则有以下转化

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

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

这个东西非常奇妙，我们通过对子集的 $\min/\max$ 的加减就得到了全集的 $\max/\min$。

证明（前一条等式）：除了 $S$ 中最大的元素的贡献为 $(-1)^{(1-1)}=1$，其他元素作为最小值出现无非就是将比它大的元素挑着选，贡献为 $\binom{n}{1}-\binom{n}{2}+\binom{n}{3}=\binom{n}{4}+\dots=0$，其中 $n$ 为集合中 $\ge$ 这个元素的数量。

Min-Max 容斥还适用于求 $\max/\min$ 的期望值，有

$$E[\max(S)]=\sum_{T\subseteq S} (-1)^{|T|-1}E[\min(T)]$$

$$E[\min(S)]=\sum_{T\subseteq S} (-1)^{|T|-1}E[\max(T)]$$

当遇到求「所有元素出现最早时间」「所有元素都出现的时间」的期望都可以转化为这一类容斥。

kth Min-max 容斥

$$\text{kth}\max(S,k)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)$$

形式类似于二项式反演。在求期望时也同样适用。

概率和期望

  • 在概率中一般使用大写字母代表一个事件，在期望中大写字母则表示一个随机变量。而小写字母则表示系数。
  • 连续随机变量：连续变量的取值可以是任意实数。
  • 离散随机变量：该随机变量可能取有限个值，即可以用一个数组来表示。

在 OI 中涉及到的大多为离散随机变量。

期望

  • (离散随机变量) 全概率公式 / 期望的定义：$E(X)=\sum\limits_{x_i}x_i·E(X=x_i)$.
  • 期望的线性性：$E(aX+bY)=a·E(X)+b·E(Y)$.
  • 两随机变量的乘积的期望：$E(EY)=E(X)·E(Y)$，其中随机变量 $X,Y$ 要相互独立。

条件概率 / 期望

  • 条件概率公式：$P(B|A)=P(A\cap B)/P(A)$，即两个事件 同时发生 的概率与前提事件发生的概率之比。
  • (离散随机变量)全期望公式：$E(X)=\sum\limits_{y_i}E(X|Y=y_i)·P(Y=y_i)$，相当于把所有的情况枚举一遍，再求期望的加权平均。

一些结论

  • 离散随机变量的几何分布：在 $n$ 次试验中，第一次成功的期望次数。即前 $(k-1)$ 次皆失败，第 $k$ 次成功的概率。容易(用等比数列求和)有 $E(x)=\sum\limits_i^\infty i·(1-p)^{1-k}p=1/p$，即 成功概率为 $p$ 的事件期望 $1/p$ 次成功。
  • 多连续随机变量第 $k$ 小期望：对于 $n$ 个取值范围为 $[0,1]$ 的随机变量 $x_1,x_2,\dots,x_n$，其中第 $k$ 小的值的期望为 $k/(n+1)$。（证明1 / 证明2 / 证明3）
  • 方差：
    • $s^2=\sum(x_i-\overline x)^2/n=\sum x_i^2-\left(\sum x_i/n\right)^2$.
    • $\mathrm{Val}(x)=E((x-E(x))^2)=E(x^2-2x·E(x)+E^2(x))=E(x^2)-E^2(x)$.

概率生成函数 $\mathbf {(PGF)}$

对于一个离散随机变量 $A$，限制其值域为 $A \in \mathbb N$.

定义其概率生成函数为

$$F(x) = \sum\limits_{i=0} P(A=i)·x^i$$

  • 由定义有 $\sum\limits_{i=0} P(A=i)=1$，因此 $F(1)=1$.
  • 可以发现，期望就是 $F$ 的一阶导的系数之和： $$E(x) = \sum\limits_{i=0} P(A=i)·i=F’(1)$$
  • 进一步地，可以推广得到 $E(x^{\underline i})=F^{(i)}(1)$.
  • $E(x^2) = E(x^{\underline 2}) + E(x^{\underline 1}) = F’’(1)+F’(1)$
  • 方差：$\mathrm{Val}(x) = E(x^2)-E^2(x) = F’’(1)+F’(1)-F’(1)^2$

下面是 PGF 的一些应用。

  • $\textbf{思想 1}$：$\mathrm {PGF}$ 的乘法

若概率生成函数 $F,G$ 分别表示随机变量 $A,B$ 的取值概率，那么 $F * G = \sum\limits_{i=0} x^i \sum\limits_{j=0}^i F[j] · G[i-j]$ 表示 $A+B$ 的取值概率。

不过这个其实也能用 OGF 来代替。

$\mathrm {PGF}$ 的加法没有意义。

  • $\textbf{思想 2}$：$\mathrm {PGF}$ 与期望的关系。

假设我们要计算一个随机变量 $A$ 的期望，那么我们定义概率生成函数 $F$ 表示随机变量 $A=i$ 的概率，另一个概率生成函数 $G$ 表示随机变量 $A>i$ 的概率。那么显然我们想要求的是 $F’(1)$.

那么我们有 $G[i]=F[i+1]+G[i+1]$，投射到整个生成函数的移动就有

$$F+G = xG+1$$

我们对两边求导就有

$$F’+G’ = xG’+G$$

我们取 $x=1$ 得到

$$\begin{aligned} F’(1)+G’(1) &= G’(1)+G(1) \ F’(1) &= G(1) \end{aligned}$$

非常神奇地，我们就得到了这样简洁的式子。因此如果要计算答案只需计算 $G(1)$ 即可。我们思考它的意义，其实就是 $E(A) = \sum\limits_{i=0} P(A >i)$.

  • $\textbf{思想 3}$：多个随机变量的 $\mathrm {PGF}$ 间关系的表示

假设现在有多个随机变量的 PGF 为 $F,G,H \dots$，我们想要计算的是 $F(1),G(1),H(1)\dots$

那么如果我们找出它们之间的关系，然后直接令 $x=1$，那么所有的 $x^i$（生成函数移位）均被消去，而生成函数 $F,G,H\dots$ 均变成了 $F(1),G(1),H(1)\dots$

现在就变成了若干个未知数的等式。那么我们推一下式子或者高斯消元即可求出各个随机变量的概率 / 期望。

Burnside 引理和 Pólya 定理

  • 好文章：OI Wiki / 好文章 / D:\1 - Training\2020D - 暑假集训\3 - 20200816\3群论与 polya.docx

(置换)群 相关定义

  • 代数系统：由若干元素组成的集合，并在上面定义若干个运算（一元运算 / 二元运算），并要求这些运算是封闭的。
  • 群：只有一个运算（通常称为乘法）的代数系统。一般用 $(G,*)$ 来表示。群满足一下性质：
  • 封闭性：$\forall a,b \in G, a*b \in G$.
  • 结合律：$\forall a,b,c \in G, (a*b)*c=a*(b*c)$.
  • 单位元：$\exists e\in G, a * e=e * a=a$.
  • 逆元：$\forall a \in G,\exists b \in G, a*b=e$.
    • 可以用反证法等推导得出：一个群 有且仅有 一个单位元，任何一个元素 有且仅有一个逆元。
    • 注意一般的群不具有交换律。
    • 置换：是对排列的一种操作，通常记作 $\begin{pmatrix} 1&2&\dots&n \\ a_1&a_2&\dots&a_n \end{pmatrix}$，其中 $a_i$ 表示第 $i$ 个元素置换后的位置为 $a_i$，可以注意到 $\left\langle a_1,a_2,\dots,a_n \right\rangle$ 也形成了一个排列。
  • 元素集：置换作用的元素即 $1\sim n$，我们记其为 $\Omega$。例如元素 $i$ 经过置换 $p=\begin{pmatrix} 1&2&\dots&n \\ a_1&a_2&\dots&a_n \end{pmatrix}$ 后该元素就变成了 $a_i$，记作 $p(i)=a_i$。
  • 置换群：定义一个群内的元素为若干个 置换，置换间的运算 $a * b$ 为先做置换 $a$，再做置换 $b$ 的等效置换(也就是 $i$ 号元素最终去到哪个位置)。
    • 任何置换群的单位元均为 $\begin{pmatrix} 1&2&\dots&n \\ 1&2&\dots&n \end{pmatrix}$.
    • $\begin{pmatrix} 1&2&\dots&n \\ a_1&a_2&\dots&a_n \end{pmatrix}$ 的逆元为 $\begin{pmatrix} a_1&a_2&\dots&a_n \\ 1&2&\dots&n \end{pmatrix}$.

轨道稳定子定理

  • 不动点：若对于元素 $k \in \Omega$ 和置换 $p$，若有 $p(k)=k$（即 $k$ 经过置换 $p$ 后还是 $k$），那么我们称 $k$ 是置换 $p$ 的不动点。记置换 $p$ 的不动点个数为 $c(p)$.
  • $k$ 不动置换类：是一个由置换组成的集合，也是原来群的一个子集。这些置换均满足 $k$ 是它们的不动点。可以证明 $k$ 不动置换类也是群（感性理解：相当于把元素 $k$ 剔除掉得到的置换），我们记作 $Z_k(\subseteq G)$。
  • 等价类：元素 $k \in \Omega$ 经过置换群内的任意多次置换可以得到的所有元素的集合，记作 $E_k(\subseteq \Omega)$。容易发现对于所有 $i\in E_k$，$E_i$ 都相等。我们也称 $E_k$ 为 $k$ 的 轨道。

轨道稳定子定理：对于任意的 $k$，均满足 $|Z_k|·|E_k|=|G|$.

我们设 $E_k = {e_1,e_2,\dots,e_n}$，我们令 $e_1=k$。由等价类定义，存在置换 $p_i$ 使得 $p_i(k)=e_i$.

显然，因为置换如何变换还是置换，所以有 $Z_k*p_1 \cup Z_k*p_2 \cup \dots \cup Z_k*p_n \subseteq G$.

同时，对于 $\forall g \in G$，因为一定会有 $g(k)=e_i$，我们总能找到一个置换 $z \in Z_k$ 使得 $z * p_i = g$（转化一下 $z = g * p_i^{-1}$）。因此 $\forall g \in G$ 总能找到一个 $z * p_i$.

因此 $G \subseteq Z_k*p_1 \cup Z_k*p_2 \cup \dots \cup Z_k*p_n$.

综上，$Z_k*p_1 \cup Z_k*p_2 \cup \dots \cup Z_k*p_n = G$.

我们同时可以知道 $Z_k*p_i \cap Z_k * p_j = \varnothing (i \neq j)$，因为前者让元素 $k$ 变为 $e_i$，后者让 $k$ 变为 $e_j$.

而任意 $|Z_k*p_i|=|Z_k|$（因为 $Z_k$ 内元素两两不等），因此 $|Z_k|*|E_k|=|G|$.

Burnside 引理

Burnside 引理内容：置换群 $(G, * )$ 的不同等价类数量 $l=\dfrac{1}{|G|} \sum\limits_{p\in G} c(p)$.

证明：我们发现

$$ \dfrac{1}{|G|} \sum\limits_{p\in G} c(p) = \dfrac{1}{|G|} \sum\limits_{p \in G} \sum\limits_{k \in \Omega} [p(k)=k] = \dfrac{1}{|G|} \sum\limits_{k \in \Omega} \sum\limits_{p \in G} [p(k)=k] = \dfrac{1}{|G|} \sum\limits_{k \in \Omega} |Z_k| $$

  • （这揭示了 $k$ 不动置换类与不动点之间的关系）

因此我们只需证明 $l=\dfrac{1}{|G|} \sum\limits_{k \in \Omega} |Z_k|$（其实就是转化了一下贡献）

因为同一等价类内的元素的 $|E_i|$ 都相等，那么 $\sum\limits_{k \in \Omega} |Z_k| = \sum\limits_{i=1}^l |Z_k|·|E_k| = \sum\limits_{i=1}^l |G| = l·|G|$.

综上：

$$\dfrac{1}{|G|} \sum\limits_{p\in G} c(p) = \dfrac{1}{|G|}\sum\limits_{k \in \Omega} |Z_k| = \dfrac{1}{|G|} · l·|G| = l$$

实战时，我们一般将等价类的元素看做本质相同方案，那么答案就为等价类个数。只要我们找出所有的置换然后直接套公式即可计算出答案。

Pólya 定理

Pólya 定理内容：对排列进行染色，我们视等价类内的排列都相同，染色总方案数为

$$\dfrac{1}{|G|} \sum_{p \in G} T(p)$$

其中 $T(p)$ 表示满足给排列染色经过置换 $p$ 之后仍与原排列染色方案相同的排列数。

证明：我们要计算染色总方案数，如果使用 Burnside 引理，那么我们应该先构造一个「对染色排列的置换群」，元素集大小为 不计置换后本质相同 时的序列染色方案数大小，而每个置换就相当于对每个排列暴力找出置换后的排列是什么。

那么染色总方案数就为 $\dfrac{1}{|G|}\sum\limits_{p\in G}c(p)$，其中 $c(p)$ 表示不动点个数，即染色排列置换后仍与原来相同的方案数。我们发现这和上面的定义一模一样。所以这是一一对应的。

因此，Pólya 定理 是 Burnside 引理的特殊形式。那么我们何必辛苦新建出这样的定理出来呢？因为这简化了思考过程，可以直接让我们计算每个置换的不动排列染色数量，而不必把每个排列当成一个元素然后再兜个圈转化回来…（感性理解?）

如何计算 $T(p)$？我们将每个置换看成一个图，建边 $i \to a_i$，就成了若干个不相交的简单环，因为需要置换后染色方案相同，因此环内所有元素都需要染同一种颜色，然后就很好计数了。

博弈论

一些定义

  • 公平组合游戏(Impartial Game)：
    • 两人参与，有先手和后手之分，二者轮流做出决策；
    • 双方均知道游戏的完整信息，任一方的决策集合只与当前的状态有关，而与游戏者无关；
    • 游戏中的同一个状态不可能多次抵达(无环)，游戏以玩家无法行动为结束，且游戏一定会在有限步后结束。
    • 双方都绝顶聪明。
  • 博弈图：我们将游戏中的每一个状态看作图上的一个点，将游戏的两个状态之间的转移（即游戏者的操作）看作一条有向边，那么整个游戏就可以视作一个 有向无环图。对于一条边 $(u,v)$，我们称状态 $v$ 为状态 $u$ 的 后继状态。
  • 必胜态与必败态(对于先手)：因为在公平组合游戏中，游戏的胜负只由游戏信息有关而与游戏者无关，所以每个游戏状态的胜负是可以预先确定的。它们在博弈图上有这样的性质：
    • 没有后继状态的游戏状态为必败态；
    • 后继状态 存在必败态 的状态为必胜态；
    • 后继状态 均为必胜态 的状态为必败态。

如果游戏状态不是很多，根据上面的性质，我们可以用类似 DAG 上 dp 的方法计算出每个状态的胜负。

Nim 和

  • Nim 游戏：有 $n$ 堆石子，一开始第 $i$ 堆石子有 $c_i$ 个石子。每次游戏者可以从一堆石子中选取一堆拿走任意多个石子。无法操作者判定为输。求先手是否必胜。

结论：若 $\bigoplus\limits_{i=1}^n c_i = 0$，那么先手必败，否则必胜。

考虑数学归纳法：

  • 当 $c_1 = c_2 = \dots = c_n = 0$ 时，先手必败。
  • 当 $\bigoplus\limits_{i=1}^n c_i \neq 0$ 时，我们设它们的异或和为 $s$，我们观察所有 $c_i$ 对应 $s$ 二进制下所在最高位的那一位，显然那一位有奇数个 $c_i$ 为 $1$，我们只要随便找出来一个满足条件的 $c_i$，它就必定满足 $c_i \oplus s < c_i$。因此我们只需取 $c_i - (c_i \oplus s)$ 个石子就能将异或和变为 $0$。
  • 当 $\bigoplus\limits_{i=1}^n c_i = 0$ 时，显然我们怎么取石子都会让异或和变为非 $0$。
  • 怎么取都会让总石子数减少。

SG 函数和 SG 定理

  • $\operatorname{mex}(S)$：为集合内最小的未出现过的 非负整数，即 $\operatorname{mex}(S) = \max{x | x \notin S, x \in \mathbb{Z}^*}$.
  • SG 函数：对于游戏的每一个状态 $u$，它的后继状态为 $v_{1 \sim m}$。我们定义其 SG 函数为 $\operatorname{SG}(x) = \operatorname{mex}{\operatorname{SG}(v_1), \operatorname{SG}(v_2), \dots, \operatorname{SG}(v_m)}$.

SG 定理(Sprague-Grundy Theorem)：对于一个博弈图，若其分成了若干个连通 DAG，设每个连通 DAG 的起点为 $s_1,s_2,\dots,s_n$，而每次玩家只能移动其中一个状态，若 $\bigoplus\limits_{i=1}^n \operatorname{SG}(s_i) = 0$，那么此时先手必败，否则先手必胜。

仍然考虑数学归纳法：

  • 显然 当所有连通子图都变成到达终止状态时 必败。
  • 若当前 $\bigoplus\limits_{i=1}^n \operatorname{SG}(s_i)\neq 0( = k) $，类似于 Nim 和的结论，我们总能找到一个 $\operatorname{SG}(s_i) \oplus k < \operatorname{SG}(s_i)$，那么就能使异或和为 $0$，将必败状态送给对方。
  • 若当前 $\bigoplus\limits_{i=1}^n \operatorname{SG}(s_i) = 0$，那么下一次异或和必定会变为非 $0$。
  • 我如果对方移动一个状态使得 $\operatorname{SG}(s_i) < \operatorname{SG}(s’_i)$，那么我们必定可以走到与原来 SG 函数相等的状态。因此 SG 函数之和可以一直减小。

对于 NIm 游戏，显然有 $\operatorname{SG}(c_i)=c_i$，其中 $c_i$ 为石子数，因为每个石子堆相互独立，因此判定式为 $\bigoplus\limits_{i=1}^n c_i =0$.

因此，我们先将游戏分割成若干个独立的有向图，然后计算每个起点的 SG 函数即可。

Nim 游戏若干模型

$\textbf{Take Away}$

每次玩家可以取一堆石子中的 $[1,k]$ 个石子。其他同普通 Nim.

我们只考虑一堆石子，那么显然有 $\operatorname{SG}(c_i) = c_i \bmod (k+1)$。多堆石子可以直接套用 SG 定理。

$\textbf{Hunger Game}$

$n$ 个箱子，第 $i$ 个箱子有 $c_i$ 个石子。每次玩家可以选择以下操作之一：1.打开若干个箱子；2. 拿走一个已打开的箱子中的任意多个石子。问先手是否必胜。

显然如果没有开箱子的设定则为普通 Nim。我们考虑先手一开始打开哪些箱子，如果打开的箱子的 SG 异或和 $\neq 0$，那么如果接下来大家都不打开箱子，先手就把必胜态送给对方了。因此我们应当一开始就打开异或和为 $0$ 的箱子。

同时，因为避免对方再开一些箱子使得异或和为 $0$，将必败态送给你，我们应当一开始把 极大的 异或和为 $0$ 的箱子全部打开。用线性基判断即可。

$\textbf{Staircase / 阶梯 Nim (1)}$

$n$ 个阶梯，第 $i$ 级阶梯阶梯上有 $c_i$ 个石子，每次玩家可以选定一个阶梯上的若干个石子放到下一级阶梯上。问先手是否必胜。

结论：偶数级阶梯上的石子相当于垃圾桶。只要对方移动偶数级阶梯上的石子，我们可以将移动的石子继续移动到下一级阶梯(还是偶数级阶梯)。

因此，我们只需要计算奇数级阶梯的石子异或和即可。

$\textbf{Staircase / 阶梯 Nim (2)}$

$n$ 个阶梯，第 $i$ 级阶梯阶梯上有 $c_i$ 个石子，每次玩家可以选定一个阶梯上的 $1$ 个石子 放到 任意一级 阶梯上。问先手是否必胜。

我们把每个石子看做一个石子堆，每次操作相当于将一个石子堆拿走若干个石子。

$\textbf{Take and Break}$

有 $n$ 堆石子，第 $i$ 堆石子的数量为 $c_i$。每次玩家可以选择 $a,b,c$ 满足 $1 \le a \le b < c \le n$，然后在第 $c$ 堆石子取出 $1$ 个石子，在第 $a,b$ 各放入 $1$ 石子。若 $a=b$ 则在同一堆放入 $2$ 个石子。问先手是否必胜。

我们将每个石子看作一个个独立的游戏，然后再用 SG 定理合并。对一个石子操作就相当于又分裂成了两个独立的游戏。

设 $\operatorname{SG}(i)$ 为石子在第 $i$ 位时的 SG 函数，那么有

$$\operatorname{SG}(i) = \operatorname{mex}\{\operatorname{SG}(j) \oplus \operatorname{SG}(k) \mid j \le k < i\}$$

思想：1. 将每个元素看成一个个独立的游戏；2. 计算 SG 函数看是否可以继续拆分成若干个独立的游戏。

$\textbf{Multi-SG}$

在 $\text{Take and Break}$ 游戏中，我们发现如果一个游戏状态的后继状态分成了若干个 独立的 子游戏，那么该游戏状态的 SG 值就是所有后继状态所有子游戏的 异或和 的 $\operatorname{mex}$.

$\textbf{Anti-SG / 反 Nim}$

获胜条件改为玩家 无法移动时 获胜。其他同普通 Nim.

如果直接套用 SG 定理，那么我们将会有 $\operatorname{SG}(0)=1$，然而两个必胜状态拼接却得到 $\operatorname{SG}(0) \oplus \operatorname{SG}(0) =0$。

$\textbf{SJ 定理(Sprague Grundy - Jia Zhihao)}$：在 $\text{Anti-SG}$ 游戏中，若游戏划分成 $n$ 个子游戏 $s_{1 \sim n}$，那么 同时满足 或 同时不满足 以下条件时先手必胜：

  1. $\bigoplus\limits_{i=1}^m \operatorname{SG}(s_i)\neq 0$
  2. $\max\{\operatorname{SG}(s_i)\}>1$

我们仍然使用归纳法证明：

证明必败状态的所有后继状态 均为 必胜状态。

  • 满足 1. 而不满足 2.：那么说明状态全由 $0/1$ 组成，且有奇数个 $1$
    • 若我们将 $0 \rightarrow 1$ 或 $1 \rightarrow 0$，那么就变为两个条件都不满足，为必胜态；
    • 若我们将其中一个改为 $>1$（注意我们将一个状态转移到一个和它 SG 函数不相等的任一状态都是可能的），那么必定会有异或和 $\ne 0$，两个条件都满足，为必胜态；
  • 满足 2. 而不满足 1.：因为有一个数 $>1$，而异或和为零 $0$，所以一定会有至少两个 $>1$ 的数，否则就无法消去更高位上的 $1$ 了。因此无论如何变换，总会有一个数 $>1$，而变换后异或和必定 $\ne 0$。为必胜态。

证明必胜状态的所有后继状态 存在 必败状态。

  • 两个条件均满足：
    • 如果只有一个 $>1$ 的数，那么我们可以把这个数转移到 $0/1$ 的状态之一。而这两个状态之一必定有一个让异或和 $\ne 0$，为必败态。
    • 如果存在两个及以上 $>1$ 的数，类似于 SG 定理的证明，我们总能找到其中一个 $>1$ 的数使得 $s_i \oplus k < s_i$（$k$ 为异或和），使得异或和为 $0$，为必败态。
  • 两个条件均不满足：那么说明状态全由 $0/1$ 组成，且有偶数个 $1$。那么我们将 $0 \rightarrow 1$ 或 $1 \rightarrow 0$，那么就满足 1. 而不满足 2.，为必败态；

$\textbf{Every-SG}$

每次玩家必须将每个尚未到达终止状态的状态 $s_i$ 进行转移。当玩家无法转移任一状态时失败。问先手是否必胜。

根据题目可以得知，我们只需要让最后一个无法移动的局面胜利即可，中间的局面失败对输赢是没有影响的。

那么我们就有这样的贪心策略：1.失败的局面步数尽量做到最小；2. 成功的局面步数尽量大。这样我们就可以让自己尽量不要失败。

因此，我们需要知道 1. SG 函数为 $0$ 的最小步数；2. SG 函数 $\ne 0$ 的最大步数。我们设 $\operatorname{step}(u)$ 为状态 $u$ 的步数，$v_i$ 为 $u$ 的后继状态，那么有：

$$\operatorname{step}(u) = \begin{cases} 0, & u \text{为终止状态}\\ \max\{\operatorname{step}(v_i) \mid \operatorname{SG}(v_i)=0\}+1, & \operatorname{SG}(u) \ne 0 \\ \min\{\operatorname{step}(v_i)\}+1, & \operatorname{SG}(u) = 0 \\ \end{cases}$$

$\textbf{Every-SG 定理}$： 当起始状态的步数的最大值为 奇数 时，先手必胜。

这是显然的。因为可以发现必败态的 $\operatorname{step}(u)$ 为偶数，必胜态的 $\operatorname{step}(u)$ 为奇数。若最大值为奇数就说明有一个局面是步数最大且必胜的。

$\textbf{k-Nim}$

每次玩家可以同时取出 $[1,k]$ 堆中的任意多个石子，其他同普通 Nim。

类似于普通 Nim，我们定义 $(k+1)$ 进制不进位加法。对于石子我们先转成二进制，然后直接视其为 $(k+1)$ 进制数。如果它们的不进位加法非 $0$，那么先手必胜，否则先手必败。

形式化表述：我们令 $c_i = \sum\limits_{j=0} d_{i,j} \times 2^j (0 \le d_{i,j} \le 1)$，若 $\forall j, \sum\limits_{i=1}^n d_{i,j} \equiv 0 \pmod {(k+1)}$，那么先手必败，否则先手必胜。

证明有点复杂。大概也是分

  1. 不进位和非零时 存在方案转移到 不进位和为零；
  2. 不进位加法为零时 不存在方案转移到 不进位和为零。

$\textbf{翻硬币游戏}$

$n$ 枚硬币排成一列，每个硬币可以正面朝上也可以反面朝上。每次玩家可以按照 一定规则 翻动一些硬币，但是必须保证 被翻动的最右边的硬币是「正面 $\rightarrow$ 反面」。问先手是否必胜。

结论：我们可以将游戏拆分成若干个仅有一个硬币是正面的游戏，然后将它们的 SG 值求异或和即为答案。eg: $\operatorname{SG}(001011) = \operatorname{SG}(001) \oplus \operatorname{SG}(00001) \oplus \operatorname{SG}(000001)$.

因为两个局面完全相同的游戏可以视作消去（异或），而最右边翻动的硬币必然是正面，而左边的硬币会从反面翻到正面 / 正面翻到反面，这相当于多了一个局面。因此这是等价的。

因此只需算出 $\operatorname{SG}(1 \sim n)$ 的值即可，根据题目的翻硬币规则来暴力求 $\operatorname{mex}$ / 找规律。

$\textbf{树上删边游戏}$

给定一棵 有根树，每次玩家可以删去一条边，然后舍弃与根不连通的部分。问先手是否必胜。

$\textbf{克朗原理(Colon Principle)}$：在树上删边游戏中，叶子节点的 SG 值为 $0$，非叶节点的 SG 值为各子树的 SG 值 $+1$ 后的异或和。

考虑归纳法：

  • 显然，只有一个节点的时候结论成立。
  • 我们当节点数量 $\le n$ 时均成立，此时我们要证明 $(n+1)$ 也成立。
    • 当根节点只有 $1$ 个儿子时，那么切割方式有两种：
      • 切断根与其仅有的一个儿子的边，那么此时后继状态 SG 值为 $0$；
      • 切断子树内的任一条边：那么此时整棵树大小 $\le n$，因此此时根节点的 SG 值为子树的任一后继状态（因为切断了一条边）的 SG 值 $+1$。相当于把子树的所有 SG 值整体 $+1$。
      • 综上，后继状态既有 $0$，也有子树所有后继状态 $+1$，因此此时结论成立。
    • 当根节点有多个子树时，容易发现，各个子树是互相独立的，因此我们可以将树分割成若干棵树，使得每个根节点仅有一个儿子，转化成了上面的情况。我们用 SG 定理合并，那么就是每个子树的异或和。

$\textbf{图上删边游戏}$

给定一棵 无向图，并选定一个 关键节点。每次玩家可以删去一条边，然后舍弃与关键节点不连通的部分。问先手是否必胜。

$\textbf{费森原理(Fusion Principle)}$：在图上删边游戏中，我们将所有偶环缩成新点，奇环缩成新点再添加一条边，原先连向环的边全部连至新点。转化成树上删边游戏。可以证明转化前后是等价的。