若字符串 $s$ 有周期 $p,q$，且 $p+q\le|s|+\gcd(p,q)$，则 $\gcd(p,q)$ 为 $|s|$ 的周期。
若 $p=q$，结论显然。否则设 $p>q$。
考虑归纳地证明。因为 $(p-q)+q\le|s|-q+\gcd(p-q,q)$，如果周期引理对于 $s$ 长为 $|s|-q$ 的后缀成立，那么 $\gcd(p-q,q)$ 是该后缀的一个周期。
又因为 $2q\le p-\gcd(p,q)+q\le|s|$，即该后缀长度不少于 $\gcd(p,q)$，所以 $\gcd(p-q,q)$ 是该后缀的周期，也就为 $s$ 长为 $q$ 的前缀的周期，并且是整周期。
所以 $\gcd(p,q)$ 为 $s$ 的周期。
LGV 引理 & Matrix Tree 定理 & BEST 定理
一个带权 DAG 上，对于某个起点序列 $A_k$ 和终点序列 $B_k$，称一组不相交路径 $S$ 为 $k$ 条路径 $A_i\to B_{\sigma_S(i)}$ 构成的集合，满足路径间两两没有公共点，其中 $\sigma_S$ 是与 $S$ 相关的一个 $k$ 阶排列。
定义一条路径 $p$ 的权值 $\omega(p)$ 为路径上所有边的边权乘积。$e(u,v)$ 表示 $u$ 到 $v$ 的所有路径的边权之和。那么有
$$\displaylines{\sum_{S}(-1)^{\tau(\sigma_S)}\prod_{i=1}^k\omega(S_k)= \begin{vmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_k)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_k)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_k,B_1)&e(A_k,B_2)&\cdots&e(A_k,B_k)\end{vmatrix} }$$其中 $\tau(\sigma_S)$ 表示 $\sigma_S$ 的逆序对数。
称左式 $\sum$ 内的部分为 $S$ 的权值。根据行列式定义，右式计算的是所有 $k$ 条路径 $A_i\to B_{\sigma_S(i)}$ 构成的路径组的权值之和，而左式是其中路径两两无公共点的路径组的权值之和。
对于一个相交的路径组 $S$，我们找出图上编号最小的出现在至少两条路径中的点 $u$，找经过它的路径中编号最小的两条边，交换它们 $u$ 以后的部分。因为交换一个排列的两个位置，排列的逆序对数奇偶改变，所以我们构造出了一个贡献完全相反的路径组 $S'$。
而且不难发现对 $S'$ 进行相同的构造可以得到 $S$，所以实际上我们获得了所有路径有相交的路径组的一组匹配，且这个匹配内相对的路径组贡献相反。所以所有路径有相交的路径组的贡献总和是 $0$。
而对于有向网格图，$A_i$ 均在第一行，$B_i$ 均在最后一行这样的只有满足 $\sigma_S(i)=i$ 的路径组 $S$ 不相交的情形，LGV 引理算出来的即 $k$ 条不相交路径 $A_i\to B_i$ 构成的路径组的权值和。
todo
给二分图的每条边染色，求最小的颜色数量，使得任何两个共顶点的边不同色。
我们构造性的证明该问题的答案为所有点度数的最大值。
首先将颜色映射到自然数。然后以任意顺序考察每条边，将其染色。我们需要保证每一步染色之后，已经染色的这些边满足限制。
对于一条边 $(u,v)$，设以 $u$ 为端点的所有边的颜色构成的集合的补集中最小的（即 $\mathrm{mex}$）为 $x$，$v$ 的为 $y$。若 $x=y$，则将边 $(u,v)$ 染成该颜色。
否则构造这样的序列：$p_0,q_1,p_1,q_2,p_2,\cdots$。其中 $p_0=u$，$q_i$ 为 $p_{i-1}$ 连出的颜色为 $y$ 的边的另一端，$p_i$ 为 $q_i$ 连出的颜色为 $x$ 的边的另一端。如果 $p_i$ 不存在连出的颜色为 $y$ 的边，或 $q_i$ 不存在连出的颜色为 $x$ 的边，则该项为序列结尾。
显然，不存在 $p_i\not=p_j,q_{i+1}=q_{j+1}$，不存在 $q_i\not=q_j,p_i=p_j$。所以这样的序列元素一定两两不同，其长度不超过总点数。
并且 $v$ 一定不在该序列中，因为 $v$ 不存在颜色为 $y$ 的边。
然后将图上每条边 $(p_i,q_{j+1})$ 的颜色改为 $x$，将 $(p_i,q_i)$ 的颜色改为 $y$。然后给 $(u,v)$ 染色为 $y$ 即可。
显然原问题答案不会小于所有点的最大度数，而上述构造方案得出的所有边的颜色不会超过所有点的最大度数，证毕。
直接按照上述过程进行构造，时间复杂度为 $O(nm)$。
可以利用它将 k-正则图分解为若干组匹配的无交并。染色后每条边的颜色即它属于哪个匹配。
对于任意两个长为 $N=2^m$ 的数列 $a,b$，令
$$\displaylines{c_i=\sum_{i=p\oplus q}a_pb_q }$$欲构造可逆线性变换 $\mathcal F_m$，对于所有 $i\in[0,N)$ 满足
$$\displaylines{\mathcal F_m(c)_i=\mathcal F_m(a)_i\cdot\mathcal F_m(b)_i }$$我们考察 $\mathcal F$ 的矩阵表达 $T$，将 $a,b,c$ 写作列向量 $\mathbf{a,b,c}$，即
$$\displaylines{(T\mathbf c)_i=(T\mathbf a)_i(T\mathbf b)_i }$$再展开得
$$\displaylines{\begin{aligned} (\sum_jT_{i,j}c_j)&=(\sum_jT_{i,j}a_j)(\sum_jT_{i,j}b_j)\\ \sum_{p,q}T_{i,p\oplus q}a_pb_q&=\sum_{p,q}T_{i,p}T_{i,q}a_pb_q \end{aligned}}$$为了让 $\mathcal F$ 对于任意的 $a,b$ 都满足这样的性质，每项 $a_pb_q$ 前的系数都要相等，即对于任意 $i,p,q$ 都有
$$\displaylines{T_{i,p\oplus q}=T_{i,p}T_{i,q} }$$不难发现 $T$ 的每一行都由这样一个方程组限制：
$$\displaylines{\begin{cases} x_{p\oplus q}=x_px_q&\forall p,q\in[0,N) \end{cases} }$$为了使得 $\mathcal F$ 可逆，我们需要对该方程组求出 $N$ 组线性无关的解。
首先有 $x_0^2=x_0$，解得 $x_0$ 为 $0$ 或 $1$。由于 $x_0=0$ 会导致所有 $x_i$ 都为 $0$，与任意一组解皆线性相关，舍去。
然后有 $x_i^2=x_0=1$，解得 $x_i=\pm1$。于是 $f(i)=x_i$ 为 $(S,\oplus)$ 到 $(\{0,\pm1\},\times)$ 两个线性空间之间的同态，其中 $S$ 表示在 $[0,N)$ 内的自然数。
于是我们取出 $(S,\oplus)$ 的一组基，指定集合中每个元素的 $x$ 值后即可得到每个位置的解。简单起见，我们指定
$$\displaylines{T_{i,2^j}=\begin{cases} 1&(\left\lfloor\frac i{2^j}\right\rfloor\bmod2=0)\\ -1&(\left\lfloor\frac i{2^j}\right\rfloor\bmod2=1)\\ \end{cases} }$$$\left\lfloor\frac i{2^j}\right\rfloor\bmod2$ 即 $i$ 二进制下第 $j$ 位上的数字。
通过观察不难发现，$T_{i,j}$ 的值即为 $(-1)^{\mathrm{popcount}(i\operatorname{AND}j)}$，其中 $i\operatorname{AND}j$ 表示按位与，$\mathrm{popcount}$ 表示二进制下 $1$ 的个数。
更进一步地，按照 $i,j$ 的二进制下第 $m-1$ 位分类讨论，可以将 $T_{i,j}$ 划分为四个方阵。可以看出 $\mathcal F_m$ 的矩阵表示 $T$ 与 $\mathcal F_{m-1}$ 的矩阵表示 $A$ 存在一定关系：
$$\displaylines{T=\begin{bmatrix} A&A\\A&-A \end{bmatrix} }$$因此求 $\mathcal F_m(a)$ 也可以依此递归进行，将 $a$ 等分成两份 $a_0,a_1$，于是 $\mathcal F_m(a)$ 的前半部分为 $\mathcal F_{m-1}(a_0)+\mathcal F_{m-1}(a_1)$，后半部分为 $\mathcal F_{m-1}(a_0)-\mathcal F_{m-1}(a_1)$。这里的加减表示序列对应位置相加减后得到一个新序列。
为了求 $T$ 的逆，我们进行消元：
$$\displaylines{\left[\begin{array}{cc|cc}A&A&1&0\\A&-A&0&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}A&A&1&0\\0&-2A&-1&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}A&0&\frac12&\frac12\\0&-2A&-1&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}1&0&\frac12A^{-1}&\frac12A^{-1}\\0&1&\frac12A^{-1}&-\frac12A^{-1}\end{array}\right] }$$即
$$\displaylines{T^{-1}=\frac12\begin{bmatrix}A^{-1}&A^{-1}\\A^{-1}&-A^{-1}\end{bmatrix} }$$此时
$$\displaylines{T_{i,j}=\frac{(-1)^{\mathrm{popcount}(i\operatorname{AND}j)}}{2^n} }$$也即得到了 $\mathcal F$ 的逆变换。
从节点 $0$ 出发，在无向图上游走，在每个节点有 $p$ 的概率终止，否则等概率走向相邻节点。
设 $f_{i,u}$ 为 $i$ 时刻之前随机游走过程未终止，而 $i$ 时刻小 P 在点 $u$ 的概率。
而 $0$ 时刻在点 $1$，于是 $f_{0,u}=[u=1]$。
而第 $i$ 时刻（$i>1$）的情况可以表示为
$$\displaylines{f_{i,u}=\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|} }$$于是最终停留在点 $u$ 的概率为
$$\displaylines{\sum_{i=0}^\infty pf_{i,u}=p\sum_{i=0}^\infty f_{i,u} }$$令
$$\displaylines{\begin{aligned} g_u&=\sum_{i=0}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\sum_{i=1}^\infty\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\sum_{i=0}^\infty f_{i,v}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v \end{aligned} }$$据此我们可以列出关于 $g$ 的方程组
$$\displaylines{\begin{cases} g_0+\sum_{v\in N(0)}\frac{1-p}{|N(v)|}\cdot g_v=1\\ g_u+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v=0&(u\neq 0) \end{cases} }$$然后使用高斯消元求解。
从节点 $0$ 出发，在无向图上游走，等概率走向相邻节点，到 $t$ 点结束，求经过每条边的期望次数。
记 $N'(u)=N(u)\setminus\{t\}$。
设事件 $A_{i,u}$ 为第 $i$ 个时刻在点 $u$，$B_{i,v,u}$ 为 $i-1$ 时刻到 $i$ 时刻间由点 $v$ 转移到了点 $u$。显然有 $P(A_{0,u})=[u=0]$。
不难发现，对于 $v\in N'(u)$ 有
$$\displaylines{P(A_{i,u}B_{i,v,u})=P(A_{i-1,v}B_{i,v,u})=P(B_{i,v,u}|A_{i-1,v})P(A_{i-1,v})=\frac{P(A_{i-1,v})}{|N'(v)|} }$$由全概率公式，易得
$$\displaylines{P(A_{i,u})=\sum_{v\in N'(u)}P(A_{i,u}B_{i,v,u})=\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|} }$$设 $f_u$ 为经过 $u$ 的期望次数，由期望的线性性可得
$$\displaylines{\begin{aligned} f_u&=\sum_{i=0}^\infty P(A_{i,u})\\ &=P(A_{0,u})+\sum_{i=1}^\infty\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\sum_{i=0}^\infty\frac{P(A_{i,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\frac{f_v}{|N'(v)|} \end{aligned} }$$由此可列出线性方程组，通过高斯消元解得答案。
数论函数定义为定义域为整数，值域为整数的函数。
常见的数论函数：
函数 $f$ 是积性函数当且仅当 $f(1)=1$，且对于任意互质的 $x,y$ 都有 $f(xy)=f(x)f(y)$。
函数 $f$ 是完全积性函数当且仅当 $f(1)=1$，且对于任意 $x,y$ 都有 $f(xy)=f(x)f(y)$。
对于两个数论函数 $f,g$，$f$ 与 $g$ 的 Dirichlet 卷积定义为
$$\displaylines{(f*g)(n)=\sum_{d|n}f(d)g(\frac nd) }$$Dirichlet 卷积具有交换律、结合律，$\varepsilon$ 为 Dirichlet 卷积的单位元。
任何 $1$ 处点值非 $0$ 的数论函数都存在 Dirichlet 卷积逆。
积性函数的 Dirichlet 卷积是积性函数，积性函数的 Dirichlet 卷积逆也是积性函数。
定义莫比乌斯函数
$$\displaylines{\mu(n)=\begin{cases}0&(\exists x>1,x^2|n)\\(-1)^{\omega(n)}&(\text{Otherwise})\end{cases} }$$莫比乌斯函数与 $1$ 互为 Dirichlet 卷积逆，即 $\mu*1=\varepsilon$。
证明：
$$\displaylines{(\mu*1)(n)=\sum_{d|n}\mu(d) }$$考虑到右式只有当 $d$ 不含平方因子时 $\mu(d)$ 才非 $0$。
设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$。显然
$$\displaylines{\begin{aligned} (\mu*1)(n) &=\sum_{T\subseteq\{p_1,p_2,\cdots p_n\}}\mu\left(\prod_{t\in T}t\right)\\ &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\\ &=\sum_{k=0}^n\binom nk(-1)^k\\ &=(1-1)^n\\ &=\varepsilon(n)\qquad\Box \end{aligned} }$$$\varphi*1=\mathrm{id}$，也即 $\sum_{d|n}\varphi(d)=n$。
证明：考虑构造 $x\in[1,n]$ 到 $\{(d,x):d|n,\gcd(x,d)=1\}$ 的映射
$$\displaylines{f:x\mapsto\left(\frac n{\gcd(x,n)},\frac x{\gcd(x,n)}\right) }$$不难发现这是一个双射。$\Box$
$\varphi=\mu*\mathrm{id}$，也即 $\sum_{d=1}^n[\gcd(n,x)=1]=\sum_{d|n}\mu(d)\cdot\dfrac nd$。
证明：设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$，由容斥原理
$$\displaylines{\begin{aligned} \sum_{d=1}^n[\gcd(d,n)=1] &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\cdot\frac n{\prod_{t\in T}t}\\ &=\sum_{d|n}\mu(d)\cdot\frac nd\qquad\Box \end{aligned} }$$设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$。有
$$\displaylines{\varphi(n)=n\prod_{i=1}^n1-\frac1{p_i} }$$证明：类似上一个结论，运用容斥原理有
$$\displaylines{\begin{aligned} \sum_{d=1}^n[\gcd(d,n)=1] &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\cdot\frac n{\prod_{t\in T}t}\\ &=n\sum_{T\subseteq\{p_1,p_2\cdots,p_n\}}\prod_{t\in T}-\frac1t\\ &=n\prod_{i=1}^n(1-\frac1{p_i}) \end{aligned} }$$事实上可以通过快速幂优化的不只有一般的矩阵乘法，将矩阵乘法中的 $+$ 和 $\times$ 替换为运算 $\oplus$ 和 $\otimes$，只要求 $\otimes$ 具有结合律、$\oplus$ 具有交换律、$\otimes$ 对 $\oplus$ 具有分配律，也可以类似地计算。
矩阵乘法一般不具有交换律，实现时应当注意乘法顺序。
求某个点到所有点的经过恰好 $L$ 条边的最小瓶颈路长度。
对邻接矩阵定义广义矩阵乘法 $\circ$：
$$\displaylines{(A\circ B)_{i,j}=\min_k\{\max(A_{i,k},B_{k,j})\} }$$不难发现 $({A^k})_{i,j}$ 表示点 $i$ 到 $j$ 的长为 $k$ 的瓶颈路长度。
Hall 定理：某个二分图 $G$ 的左右两部点集分别为 $V_1,V_2$，那么 $V_1$ 存在完美匹配当且仅当对于任意 $S\subset V_1$ 均有 $|S|\le|\cup_{u\in S}N(u)|$。
后者的必要性是显然的，现在证明其充分性。任取一个最大匹配，设其中与某个右部点 $v$ 相匹配的点为 $\hat v$。若存在左部点 $k$ 不在最大匹配中，构造点集 $S_0=\{k\}$ 和 $S_t=\{\hat v\mid v\in \cup_{u\in S_{t-1}}N(u)\}\cup\{k\}$（考虑到，对于任意 $u\in S_{t-1}$，任意 $v\in N(u)$ 均有与它匹配的左部点，否则总能按照集合扩展的路径构造出一条增广路使得答案增加）。
对于某个 $t$，令 $T=\{\hat v\mid v\in\cup_{u\in S_{t-1}}N(u)\}$。不难发现 $|T|=|\cup_{u\in S_{t-1}}N(u)|\ge|S_{t-1}|$，并且 $k\not\in|T|$。于是有 $|S_t|>|S_{t-1}|$，于是总存在某个 $t$ 使得 $|S_t|>|V_1|$，矛盾。
霍尔定理的一个简单推论是，一个二分图 $G$ 左右部点集为 $V_1,V_2$，其最大匹配数为 $|V_1|-\max_{S\subseteq V_1}(|S|-|N(S)|)$。
考虑这样一个图 $G'$，它在原图的基础上，向右部点中加入 $k=\max_{S\subseteq V_1}(|S|-|N(S)|)$ 个点 $T$，连向所有左部点。$G$ 满足 $\forall S,|S|-|N(S)|\le a$，则 $G'$ 满足 $\forall S,|S|-|N(S)|\le0$。根据霍尔定理，$G'$ 一定存在一个左部点的完美匹配，我们删去所有涉及 $T$ 中点的匹配，能够得到一组不小于 $|V_1|-k$ 的匹配。
而图中至少存在一个左部点集合 $|S|$ 使得 $|S|-|N(S)|=k$，对于任何一组匹配，这个集合中至少有 $k$ 个点没有匹配，所以最大匹配数不超过 $|V_1|-k$。
综上，$G$ 的最大匹配数为 $|V_1|-k$。
二分图中，最小点覆盖数等于最大匹配数。
首先，最大匹配的端点两两不同，所以至少需要最大匹配数的点来覆盖最大匹配的所有边。即最小点覆盖数不小于最大匹配数。
考虑依据二分图的任一最大匹配构造点覆盖。我们考察这样一条路径：
从某一未匹配的 $u_0$ 出发，到右侧一相邻节点 $v_1$，再到 $v_1$ 的匹配节点 $u_1$，再到 $u_1$ 右侧一相邻节点 $v_2$……重复这个过程直到无法再走下去，构成一条形如 $u_0\to v_1\to u_1\to v_2\cdots$ 的路径。
不难发现路径不会结束在某个右侧点 $v_n$，否则我们从原匹配中删除 $(u_1,v_1),(u_2,v_2),\cdots,(u_{n-1},v_{n-1})$，加入 $(u_0,v_1),(u_1,v_2),\cdots,(u_{n-1},v_n)$，可以构成一个比原匹配恰好大 $1$ 的匹配。
如果找出所有这样的路径，那么由左侧点中不存在于任意一条路径上的，和右侧点中存在于至少一条路径上的点构成一组点覆盖。这是显然的，如果一条边被某条路径所包含，那么它的右端点会覆盖它；如果它不被任何一条路径包含，那么它的左端点会覆盖它。
我们再证明这样构造出来的点覆盖大小等于最大匹配数。构造从该最大匹配到该点覆盖的映射 $f$：如果这条匹配边被某条路径所包含，它映射到这条边的右端点；如果这条匹配边不被任何一条路径包含，那么映射到它的左端点。
匹配边不会共用端点，所以 $f$ 是单射；根据所构造路径的性质，每个右侧点都会被它的匹配边映射到，每个左侧点也一定会存在一条匹配边（否则它会成为至少一条路径的起点），它会被这条匹配边映射到。$f$ 为双射，得证。
最小点覆盖数不会大于最大匹配数，而我们已经构造出来了一组大小等于最大匹配数的点覆盖，因此定理得证。
显然取任一点覆盖的补集都能唯一地得到一组独立集，因此最大独立集数等于点数减去最小点覆盖数。
最大独立集要求集合内不存在边，最大团要求集合内任意两点都存在一条边。因此一个图的最大团即其补图的最大独立集。
不相交链覆盖：用最少的不相交的链覆盖 DAG 上的所有点。
路径数等于点数减去边数，所以我们需要最大化连的边数。而每条边最多只能连一条入边、一条出边。所以我们用两个点分别代表这个点的“入口”和“出口”，二分图匹配。入口匹配上的点即该点在链上的前驱，入口没有匹配代表其为链起点；出口类似。
可相交链覆盖：用最少的链覆盖 DAG 上的所有点。
这里的做法很巧妙：求出原图 $G$ 的传递闭包 $G'$，$G'$ 中 $u,v$ 间有边当且仅当 $G$ 中存在路径 $u\to v$。
此时传递闭包 $G'$ 的最小不可重路径覆盖数量 $x$ 等于原图 $G$ 的可重路径覆盖数量 $y$。证明如下：
通过 $G'$ 上的不可重路径覆盖方案 $F$ 构造出 $G$ 上的可重路径覆盖是简单的，将 $F$ 中的每条路径上的每条边 $(u,v)$ 替换为 $G$ 上的路径 $u\to v$，这样不会使得路径数量改变。所以 $x\ge y$。
通过 $G$ 上的可重路径覆盖方案 $F$ 构造出 $G'$ 上的不可重路径覆盖，考虑重复以下过程直到不存在一个点被两条路径覆盖：找到这样的点 $u$ 和覆盖它的路径 $p,q$，如果 $p$ 长度为 $0$ 则将其从路径集合中删去；如果 $u$ 为 $p$ 的起点或终点，将 $u$ 从 $p$ 中删去；否则找到 $u$ 在 $p$ 中的前驱 $i$ 和后继 $j$，将 $p$ 中的边 $(i,u),(u,j)$ 替换为 $(i,j)$ 即可。这样的过程每进行一轮都会导致路径集合变小或某条路径长度减小，所以这样的过程一定能够在有限步内结束。整个过程中路径数量不会增大，所以 $x\le y$。$\Box$
博弈相关定义参考：博弈论简介 - OI Wiki
我们抛开这个游戏的任何实质性内容（规则、状态），只着眼于每个状态所构成的图结构。
那么任何游戏都可以看作是“某个标记沿着图上的边移动”的过程。
并且对于公平组合游戏，我们只需知道这个图的构造，我们就可以依照下面两条显然的性质判定每个点是必胜点还是必败点。
我们也可以根据这两个条件互为否定得出，这个图上的每个点一定是必胜点或必败点之一。
并且我们可以用某个点的所有后继节点（亦作为一个集合）构成的集合，形式化地描述任意一个 DAG 上的所有点。
那么两个能够由 DAG 描述的游戏的复合（这个游戏的每一步是在两个游戏中选一个进行）应当如下定义：
$$\displaylines{A+B=\{a+B\mid a\in A\}\cup\{A+b\mid b\in B\} }$$所有的一般胜利条件下的公平组合游戏都能转换成 Nim 数表达的 Nim 游戏。
一个公平组合游戏的 Nim 数（即 SG 函数）定义为这个博弈的等价 Nim 数。
证明见 Sprague–Grundy theorem - Wikipedia。
更多典例：博弈论小计 - command block。
当 $n$ 堆石子个数异或和为 $0$ 时该状态为必败状态，否则为必胜状态。
证明见 Nim 和 - OI Wiki。
每次取石子的堆数在 $[1,d]$ 范围内。
将每个石子堆的个数写成二进制形式并右侧对齐，如果每一位之和都是 $d+1$ 的倍数则为必败态，否则为必胜态。
限制每次取的石子个数在 $[L,R]$ 范围内。
这个游戏的 SG 函数为
$$\displaylines{\left\lfloor\frac{x\bmod(L+R)}L\right\rfloor }$$证明见 ABC297G Editorial。