数论函数定义为定义域为整数，值域为整数的函数。

常见的数论函数：

• 单位函数 $\varepsilon(n)=[n=1]$
• 常数函数 $k(n)=k$
• 恒等函数 $\mathrm{id}_k(n)=n^k$，$\mathrm{id}_0$ 简记作 $\mathrm{id}$
• 除数函数 $\sigma_k(n)=\sum_{d|n}d^k$，$\sigma_0$ 简记作 $d$，$\sigma_1$ 简记作 $\sigma$
• 欧拉函数 $\varphi(n)$ 表示 $[1,n]$ 中与 $n$ 互质的数
• 莫比乌斯函数 $\mu(n)$

函数 $f$ 是积性函数当且仅当 $f(1)=1$，且对于任意互质的 $x,y$ 都有 $f(xy)=f(x)f(y)$。

函数 $f$ 是完全积性函数当且仅当 $f(1)=1$，且对于任意 $x,y$ 都有 $f(xy)=f(x)f(y)$。

Dirichlet 卷积

对于两个数论函数 $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} }$$

对图的邻接矩阵应用矩阵乘法，限制路径上的边数做计数/最优化时，相当于每条边的边权为 $1$。但此时图具有边权，所以考虑把每条边拆成一条长为边权的链。这样点最多有 $(w-1)m+n$ 个，无法接受。于是我们考虑把从同一个点出发的边拆成的链进行合并。具体地，从每个点 $u$ 引出一条长为 $w$ 的链，然后从链上相应的节点连向 $u$ 的后继 $v$。

邻接矩阵做矩阵乘法需要记录边权，而此题需要对点权求最值。所以将每条边的边权定义为终点的点权，节点 $1$ 的点权单独统计。

美食节的处理看作点权修改，也即边权修改，快速幂过程中对于具有修改的时刻进行特殊处理即可。

期望 DP，只维护合法的状态。

每次询问暴力做矩阵快速幂会超时，所幸，对于所有询问，要做快速幂的矩阵是相同的，并且我们只需要向量乘矩阵幂后的结果。所以可以预处理出快速幂所需要的中间量，即 $A^{2^k}$ 处的取值，快速幂就只需 $\log n$ 次向量乘矩阵，时间开销由 $O(Tm^3\log n)$ 优化为 $O(m^3\log n+Tm^2\log n)$。

问题形式

• 递推式较大项求值
• 动态 DP
• 图上计数/最优化

做法

• 递推式 & 动态 DP：求出系数矩阵，利用矩阵快速幂进行计算，或使用线段树动态维护
• 图上计数：邻接矩阵的 $k$ 次幂，表示两点间长度为 $k$ 的路径条数。
• 矩阵树定理。

事实上可以通过快速幂优化的不只有一般的矩阵乘法，将矩阵乘法中的 $+$ 和 $\times$ 替换为运算 $\oplus$ 和 $\otimes$，只要求 $\otimes$ 具有结合律、$\oplus$ 具有交换律、$\otimes$ 对 $\oplus$ 具有分配律，也可以类似地计算。

矩阵乘法一般不具有交换律，实现时应当注意乘法顺序。

典例

[ABC236G] Good Vertices

求某个点到所有点的经过恰好 $L$ 条边的最小瓶颈路长度。

对邻接矩阵定义广义矩阵乘法 $\circ$：

$$\displaylines{(A\circ B)_{i,j}=\min_k\{\max(A_{i,k},B_{k,j})\} }$$

不难发现 $({A^k})_{i,j}$ 表示点 $i$ 到 $j$ 的长为 $k$ 的瓶颈路长度。

问题形式

解 $n$ 元一次不等式组，每个不等式形如 $x_i-x_j\le k$。

• 求是否有解
• 给定解的上/下限，求最大/最小解

方法

用最短路的性质（$(u,v,w)\in G\Rightarrow \operatorname{dis}_v\le\operatorname{dis}_u+w$）保证解符合方程（最长路同理）。

1. 最大解问题转化为最短路，最小解问题转化为最长路。
2. 将不等式转化为最短路/最长路性质的形式，建边。
3. 建立源点，向每个节点连出一条长为上/下限的边。
4. 求单源最短路/最长路，结果就是不等式组的最大/最小解

如果只要求判定是否有解，3、4 步删去，用 SPFA 判定是否有负环/正环。

典例

[SCOI2011] 糖果

因为建完图之后任意边的边权非负，所以一个环内出现正权极为无解，强连通分量缩点后拓扑排序求最长路。

性质

完美匹配

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$。

最小点覆盖（König 定理）

二分图中，最小点覆盖数等于最大匹配数。

首先，最大匹配的端点两两不同，所以至少需要最大匹配数的点来覆盖最大匹配的所有边。即最小点覆盖数不小于最大匹配数。

考虑依据二分图的任一最大匹配构造点覆盖。我们考察这样一条路径：

从某一未匹配的 $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 上的所有点。

路径数等于点数减去边数，所以我们需要最大化连的边数。而每条边最多只能连一条入边、一条出边。所以我们用两个点分别代表这个点的“入口”和“出口”，二分图匹配。入口匹配上的点即该点在链上的前驱，入口没有匹配代表其为链起点；出口类似。

可相交链覆盖：用最少的链覆盖 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\} }$$

SG 定理

所有的一般胜利条件下的公平组合游戏都能转换成 Nim 数表达的 Nim 游戏。

一个公平组合游戏的 Nim 数（即 SG 函数）定义为这个博弈的等价 Nim 数。

证明见 Sprague–Grundy theorem - Wikipedia。

典例

更多典例：博弈论小计 - command block。

Nim 游戏

当 $n$ 堆石子个数异或和为 $0$ 时该状态为必败状态，否则为必胜状态。

证明见 Nim 和 - OI Wiki。

K-Nim 游戏

SDOI2011 黑白棋

每次取石子的堆数在 $[1,d]$ 范围内。

将每个石子堆的个数写成二进制形式并右侧对齐，如果每一位之和都是 $d+1$ 的倍数则为必败态，否则为必胜态。

限制取子个数的 Nim 游戏

ABC297G

限制每次取的石子个数在 $[L,R]$ 范围内。

这个游戏的 SG 函数为

$$\displaylines{\left\lfloor\frac{x\bmod(L+R)}L\right\rfloor }$$

证明见 ABC297G Editorial。