OI中的数学:从入门到入土(更新)

· · 算法·理论

OI 中常用数学算法整理

前言

OI 中有许多数学相关算法,由浅入深,层层递进。本文意在整理一系列 OI 中常用的数学算法、定理与 trick。若有问题,欢迎指出。

数论

一、exgcd

算法

扩展欧几里得算法(exgcd)一般用于求解形如

ax+by=c

的不定方程。

首先,若 \gcd(a,b)\nmid c,则左侧一定是 \gcd(a,b) 的倍数,而右侧一定不是,此时方程无解。

不妨左右同除 \gcd(a,b),此时只要解决形如 ax+by=1 的问题,再左右同时乘 c 就一定可以求出 ax+by=c 的解,下面只考虑 ax+by=1。

考虑欧几里得算法求 \gcd 的过程。由于 \gcd(a,b)=1,因此递归结束时一定有 a=1,b=0。

考虑递归过程,相当于从 ax+by=1 的问题转化为 bx+(a\bmod b)y=1 的问题。

那么就需要利用 bx+(a\bmod b)y=1 的答案来计算。考虑如何构造一组解满足 ax+by=1。

将原式中的模拆开,有

\begin{aligned} bx'+(a\bmod b)y'&=1,\\ bx'+\left(a-\left\lfloor\frac{a}{b}\right\rfloor b\right)y'&=1,\\ bx'+ay'-\left\lfloor\frac{a}{b}\right\rfloor by'&=1,\\ b\left(x'-\left\lfloor\frac{a}{b}\right\rfloor y'\right)+ay'&=1. \end{aligned}

于是有 x=y',y=x'-\left\lfloor\frac{a}{b}\right\rfloor y'。

如此递归下去,就能构造出 ax+by=1 的一组解。

应用

exgcd 可以用来求模意义下的逆元,尤其是当模数不是质数时比较好用。

设模数为 p,不妨将原式改为 ax+py=1。在模 p 意义下 py\equiv 0\pmod p,此时有 ax\equiv 1\pmod p。

二、欧拉函数

定义

欧拉函数 \varphi(x) 的定义为满足 1\le i\le x 且 \gcd(i,x)=1 的正整数 i 的数量。

算法

单点求 \varphi(x)

考虑 \varphi(x) 的定义。若 \gcd(i,x)\ne 1,那么 i 就不能算入 \varphi(x)。

于是可以枚举 x 的所有质因数,此时这个质因数的所有倍数都不合法。

考虑容斥,有

\varphi(x)=x\prod_{p\mid x}\left(1-\frac{1}{p}\right),

其中 p 取遍 x 的所有质因数。

感性理解:一个质因数 p 的倍数一定都被删去,相当于在不超过 x 的数中删去了占比为 \frac{1}{p} 的数。

于是直接枚举所有质因数即可,复杂度为 O(\sqrt x)。

欧拉筛求 \varphi(x)

观察定义,并考虑欧拉筛的过程。

若 x=y\times p,有以下两种情况:

于是在欧拉筛的过程中预处理即可,复杂度为 O(n)。

根据上面的观察,同理可得:若 \gcd(x,y)=1,则 \varphi(xy)=\varphi(x)\varphi(y)。这是一个较为特殊的性质。我们称这类函数为积性函数,关于这部分将在后文详细展开。

应用与 trick

有一个和欧拉函数相关的定理:欧拉定理。

若 \gcd(a,m)=1,则

a^{\varphi(m)}\equiv 1\pmod m.

考虑一个模 m 的既约剩余系,即与 m 互质的集合,其大小一定是 \varphi(m)。

将集合中元素全部乘 a,此时这个集合仍然是既约剩余系。证明分为两部分。设某个元素为 x。

因此该定理得证。这个定理在后面有关阶的性质中会用到。

同时,欧拉函数可以求解一些有关 \gcd 的问题。例如

\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=k]

与

\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j).

第一个式子可以转化为

\sum_{i=1}^{\lfloor n/k\rfloor}\sum_{j=1}^{\lfloor n/k\rfloor}[\gcd(i,j)=1].

由于 i,j 对称,于是也可以只处理 i\ge j 的情况,这其实就是欧拉函数的定义。

对于第二个式子,一个经典 trick 是考虑 \gcd 的取值,多枚举一个 d,也就是说原式变为

\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]\times d.

将 d 提出,得到

\sum_{d=1}^n d\left(\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]\right).

内部就是第一个例子,解决方法是对 \varphi 求前缀和。

这是一个很经典也很重要的小技巧,在后面莫比乌斯反演的问题中也经常用到。

值得一提的是,以上两个问题均可以使用莫比乌斯反演解决。

三、中国剩余定理

算法

中国剩余定理常常用来解决同余方程组相关的问题。

例如

\begin{cases} x\equiv 2\pmod 3,\\ x\equiv 3\pmod 5,\\ x\equiv 5\pmod 7,\\ x\equiv b_i\pmod{a_i}. \end{cases}

求解最小的 x。

解决这一问题的核心想法是构造 T_i,使其满足:

若可以做到,答案加上 b_i\times T_i 就能满足 x\bmod a_i=b_i。

考虑取 \prod_{j\ne i}a_j 作为 T_i,但不能保证 T_i\equiv 1\pmod{a_i},暂且记作 T_i'。

由于希望其对 a_i 取模为 1,还要求它是 T_i' 的倍数,于是可以取 T_i' 在模 a_i 意义下的逆元,并与 T_i' 相乘,得到 T_i。

扩展中国剩余定理(exCRT)

刚才的做法需要对 a_i 取逆元,这就要求 a_i 两两互质。若 a_i 不互质,还可以做吗?

使用扩展欧几里得算法中的一些技巧,将原问题转为求解

x=q_i a_i+b_i=q_j a_j+b_j.

若 \gcd(a_i,a_j)\nmid(b_j-b_i),则原方程无解。

否则求出一组解 (p,q),此时相当于将两个方程合并为

x\equiv a_i p+b_i\pmod{\operatorname{lcm}(a_i,a_j)}.

重复上述过程,合并为唯一的方程即为答案。

四、整除分块

算法

整除分块可以在 O(\sqrt n) 时间复杂度内解决形如

\sum_{i=1}^n g(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

的一些问题。

以 f(x)=x,g(x)=1 为例,直接暴力枚举复杂度是 O(n)。

在这个过程中可以发现大量 f(x) 是相同的,但却重复计算了很多次。因此希望快速计算一段 f(i) 相同的答案。

假设当前枚举到的位置是 l,有哪些位置满足

\left\lfloor\frac{n}{x}\right\rfloor=\left\lfloor\frac{n}{l}\right\rfloor?

可以发现,当

x=\left\lfloor\frac{n}{\lfloor n/l\rfloor}\right\rfloor

时,取到满足 \lfloor n/x\rfloor=\lfloor n/l\rfloor 的 x_{\max}。

由于 ab\le n 的充要条件是 a\le \lfloor n/b\rfloor,代入原式即为右端点。

因此 [l,r] 这段区间的函数值都为 f(\lfloor n/l\rfloor),而这段区间一共有 r-l+1 个数,于是这一段答案为

(r-l+1)f\left(\left\lfloor\frac{n}{l}\right\rfloor\right).

时间复杂度是 O(\sqrt n)。考虑 i 的分界点:

这两部分复杂度都为 O(\sqrt n)。

小技巧

若原式变为上取整,可以利用

\left\lceil\frac{n}{x}\right\rceil=\left\lfloor\frac{n-1}{x}\right\rfloor+1

将其变为下取整形式。

另外,也可以处理不只有一项整除的函数 f,例如

f(i)=\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor.

此时需要这两项整除都相等才能快速计算,因此实际上就是取这两个位置所在块的右端点最小值,此时这段 [l,r] 的函数值都相等。

应用

有时需要转化式子,变成一些与整除有关的问题,此时可以尝试整除分块。

例如

\sum_{i=1}^n\sum_{j=1}^m(n\bmod i)(m\bmod j)\quad(i\ne j).

不难发现原式等于

\left(\sum_{i=1}^n(n\bmod i)\right)\left(\sum_{j=1}^m(m\bmod j)\right)\quad(i\ne j).

对于单独的一项,可以用

n\bmod i=n-\left\lfloor\frac{n}{i}\right\rfloor i

进行整除分块。

唯一问题就是计算了 i=j 时的答案,考虑减去这部分,即

\sum_{i=1}^{\min(n,m)}(n\bmod i)(m\bmod i).

将其展开就得到了两个一维整除分块的形式,以及一个二维整除分块的形式。

值得一提的是,在莫比乌斯反演中经常会使用整除分块。

五、阶与原根

本章内容均在 \gcd(a,m)=1 的前提下说明。

阶

定义

当 a^n\equiv 1\pmod m 时的最小正整数 n,称为 a 模 m 的阶。

记作 \delta_m(a) 或 O(a)。本文会同时使用这两种记号。

性质 0

对于 a^n\bmod m,n 一定可以表示为

n=q\delta_m(a)+r,\quad 0\le r<\delta_m(a).

显然有

a^n\equiv a^r\pmod m.

性质 1

若 $a^i\equiv a^j\pmod m$,则 $a^{j-i}\equiv 1\pmod m$。 但 $0<j-i<\delta_m(a)$,矛盾。 #### 性质 2 $a^n\equiv 1\pmod m$ 与 $\delta_m(a)\mid n$ 等价。 若 $n=\delta_m(a)+r$ 且 $r\ne 0$,则矛盾。 由欧拉定理 $a^{\varphi(m)}\equiv 1\pmod m$,可得 $$ \delta_m(a)\mid\varphi(m). $$ #### 性质 3 $$ \delta_m(a^k)=\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}. $$ 若 $(a^k)^n=a^{kn}\equiv 1\pmod m$,则 $$ \delta_m(a)\mid nk. $$ 左右同除 $\gcd(\delta_m(a),k)$,令其为 $\delta_m'(a)$,并令 $k'=k/\gcd(\delta_m(a),k)$。 由于 $\gcd(\delta_m'(a),k')=1$,于是有 $\delta_m'(a)\mid n$。 因此 $$ n_{\min}=\delta_m'(a)=\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}. $$ #### 性质 4 $$ \frac{\operatorname{lcm}(\delta_m(a),\delta_m(b))}{\gcd(\delta_m(a),\delta_m(b))}\mid\delta_m(ab)\mid\operatorname{lcm}(\delta_m(a),\delta_m(b)). $$ 因为 $$ (ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1\pmod m, $$ 所以 $$ \delta_m(ab)\mid\operatorname{lcm}(\delta_m(a),\delta_m(b)). $$ 又 $$ 1\equiv(ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)}\pmod m, $$ 所以 $$ \delta_m(a)\mid\delta_m(ab)\delta_m(b). $$ 左右同除 $\gcd(\delta_m(a),\delta_m(b))$,得 $$ \frac{\delta_m(a)}{\gcd(\delta_m(a),\delta_m(b))}\mid\delta_m(ab). $$ 由对称性亦有 $$ \frac{\delta_m(b)}{\gcd(\delta_m(a),\delta_m(b))}\mid\delta_m(ab). $$ 由于 $$ \gcd\left(\frac{\delta_m(a)}{\gcd(\delta_m(a),\delta_m(b))},\frac{\delta_m(b)}{\gcd(\delta_m(a),\delta_m(b))}\right)=1, $$ 于是 $$ \frac{\delta_m(a)\delta_m(b)}{\gcd^2(\delta_m(a),\delta_m(b))}\mid\delta_m(ab), $$ 即 $$ \frac{\operatorname{lcm}(\delta_m(a),\delta_m(b))}{\gcd(\delta_m(a),\delta_m(b))}\mid\delta_m(ab). $$ 根据上述过程容易得到一个更特殊的情况:若 $\gcd(\delta_m(a),\delta_m(b))=1$,则 $$ \delta_m(ab)=\delta_m(a)\delta_m(b). $$ #### 应用 原根中的许多定理证明会使用关于阶的性质。 ### 原根 当 $m$ 是一个质数时,有 $$ \varphi(m)=m-1. $$ #### 定义 若 $O(a)=\varphi(m)$,则称 $a$ 是模 $m$ 的一个原根。 #### 性质 原根与阶的特殊性在于它们满足 $b_i=a^i$,且 $b_i^k\equiv 1\pmod m$,即模意义下的“单位根”。 其中原根更为特殊,其保证了上述 $k$ 可以取到 $\varphi(m)$。由于 $O(a)\mid\varphi(m)$,因此所有非原根的幂次集合一定是原根幂次集合的子集。这里建议结合复数单位根理解。 设 $O(a)=k$。由阶的性质 3 可得 $$ O(a^m)=\frac{k}{\gcd(k,m)}. $$ 若 $O(a^i)=k$,则 $\gcd(i,k)=1$,共有 $\varphi(k)$ 个这样的 $i$。 因此对于任意 $k$,满足 $O(a)=k$ 的元素个数 $cnt_{O(a)=k}$ 为 $0$ 或 $\varphi(k)$。 由于每个数都有阶,于是 $$ \sum cnt_{O(a)=i}=\varphi(m). $$ 因为 $O(a)\mid\varphi(m)$,所以 $$ \varphi(m)=\sum_i cnt_{O(a)=i} =\sum_{i\mid\varphi(m)} cnt_{O(a)=i} \le\sum_{d\mid m}\varphi(d)=m. $$ 其中最后一步使用了恒等式 $$ \sum_{d\mid n}\varphi(d)=n. $$ 这里给出两个证明方法。 - 证明 1:构造函数 $f(i)=\frac{i}{n}$,取 $1\le i\le n$,对 $f(i)$ 约分。记 $g(d)$ 表示约分后分母为 $d$ 的数量。约分后分母仍是 $n$ 的约数,故有 $n=\sum_{d\mid n}g(d)$。考虑 $g(d)$:分子小于分母,且分子与分母互素,因此 $g(d)=\varphi(d)$。原定理得证。 - 证明 2:某个人写了一个这样的式子 $$ \sum_{i=1}^n \gcd(i,n) \to(?) \sum_{d \mid n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}[\gcd(i,j)=1] =\sum_{d\mid n} \varphi(i) = n? $$ 这启发我们使用这一视角证明,考虑 $$ \sum_{i=1}^n\gcd(i,n) =\sum_{d\mid n}\sum_{i=1}^{\lfloor n/d\rfloor}[\gcd(i,d)=1] =\sum_{d\mid n}\varphi(d). $$ 该式等价于和 $n$ 所有因数互质的数量,显然不超过 $n$。若 $i\perp n$,则已经结束;否则同除 $\gcd(i,n)$,一定与 $n'$ 互质。因此原定理得证。 #### 技巧 要找到所有原根,实际上,对于一个原根的判定,并不需要枚举 $1\to\varphi(m)-1$ 检查是否存在 $a^i\equiv 1\pmod m$,只需枚举其所有质因数,然后检验 $$ a^{\frac{\varphi(m)}{p_i}}\equiv 1\pmod m $$ 是否成立。 更进一步,不需要枚举所有的 $1\to\varphi(m)$,只需要找到第一个原根 $g$。然后只要满足 $\gcd(i,\varphi(m))=1$,那么 $g^i$ 也是原根。而原根数量只有 $\varphi(\varphi(m))$ 个,枚举即可。 王元证明了最小原根不超过 $O(m^{1/4})$ 级别。事实上,很多数的最小原根非常小,比如 $998244353$ 的原根只有 $3$。特别地,$114514$ 是 $998244353$ 的一个原根。 #### 应用 原根有着和复数单位根相似的性质,因此在数论中可以替代单位根。例如,NTT 就是使用原根替代复数单位根。 ## 六、BSGS ### 算法 感觉上 BSGS 更像一个分块算法。 BSGS 用于解决 $$ a^x\equiv b\pmod m $$ 的问题。 考虑到可以将 $x$ 表示为 $qB-r$ 的形式,此时原问题就是 $$ a^{qB}\equiv a^r b\pmod m. $$ 考虑将 $a^{0\to B-1}$,即原来的 $r$ 的取值范围,和 $a^{(1\to n/B)\times B}$,即 $qB$ 的取值范围预处理。这样就可以拼出所有的 $a^x$,复杂度为 $O(B+n/B)$。$B$ 取 $\sqrt n$ 时最优,复杂度为 $O(\sqrt n)$。预处理部分使用 `unordered_map` 记录即可。 ### 扩展 BSGS(exBSGS) 考虑 BSGS 的算法建立在 $a$ 有逆元的前提上,但当 $\gcd(a,m)\ne 1$ 时,$a$ 不一定有逆元。 当 $\gcd(a,m)\nmid b$ 时,此时无解。 否则,将原式左右同除 $\gcd(a,m)$,则有 $$ \frac{a}{\gcd(a,m)}a^{x-1}\equiv\frac{b}{\gcd(a,m)}\pmod{\frac{m}{\gcd(a,m)}}. $$ 令 $m'=\frac{m}{\gcd(a,m)}$。 此时若 $\gcd(a,m')\ne 1$,则重复上述过程。 最后形式一定形如 $$ \frac{a^k}{D}a^{x-k}\equiv 1\pmod{\frac{m}{D}}, $$ 此时 $\gcd\left(\frac{a^k}{D},\frac{m}{D}\right)=1$,一定有逆元,问题转化为一般的 BSGS。 ## 七、狄利克雷卷积 ### 积性函数 在第二节中发现 $\varphi(x)$ 满足:若 $\gcd(x,y)=1$,则 $\varphi(xy)=\varphi(x)\varphi(y)$。 抽象一下,定义当 $\gcd(x,y)=1$ 且 $f(xy)=f(x)f(y)$ 时,$f(x)$ 是一个积性函数。这里只考虑定义域为正整数的情况。 特别地,若函数不需要 $\gcd(x,y)=1$ 的约束,即对于任意 $x,y$,都有 $f(xy)=f(x)f(y)$,则称 $f(x)$ 是一个完全积性函数。 以下是几个完全积性函数的例子: - $\epsilon(x)=[x=1]$,只有 $x=1$ 时函数值为 $1$; - $I(x)=1$,任何 $x$ 都是 $1$; - $\operatorname{id}(x)=x$。 这几个函数的积性都不难证明。 以下是几个常用积性函数的例子: - $\varphi(x)$,前文已经介绍过了; - $\mu(x)$,也称莫比乌斯函数,定义为 $$ \mu(x)= \begin{cases} 0,&d^2\mid x,\\ (-1)^k,&d^2\nmid x, \end{cases} $$ 其中 $k$ 是将 $x$ 唯一分解后的质因数个数。积性由定义证明显然。 $\mu$ 的另一种理解是,它相当于对质数做容斥时的容斥系数,这对后面的理解有一定帮助。 ### 狄利克雷卷积 定义 $\ast$ 表示两个函数的卷积。设 $h=f\ast g$,定义 $$ h(n)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right). $$ 当上面介绍的积性函数代入到狄利克雷卷积的式子中,会产生一系列化学反应。例如: - $\mu\ast I=\epsilon$; - $\varphi\ast I=\operatorname{id}$; - $\mu\ast\operatorname{id}=\varphi$; - $f\ast\epsilon=f$。 其中第二个式子本质就是 $$ \sum_{d\mid n}\varphi(d)=n, $$ 前文已经证明。下面来证明其余三个式子。 #### 式子 1 $$ \mu\ast I=\epsilon. $$ - 当 $x=1$ 时显然成立; - 当 $x\ne1$ 时,即证明 $\sum_{d\mid n}\mu(d)=0$。 如果原式有平方因子,根据 $\mu$ 的定义,含有平方因子的项等于零,等价于所有质因子都只有一个的情况。 设 $\sum_{d\mid n}\mu(d)=x$,那么 $$ \sum_{d\mid pn}\mu(d) =\sum_{d\mid n}\mu(d)+\sum_{d\mid n}\mu(pd) =x+(-x)=0. $$ 第一个等号原因是要么含有 $p$,要么不含;第二个等号是 $\mu$ 的定义。 也可以从质数容斥的视角来看这个问题,原式等价于 $$ \sum_{d=0}^k(-1)^d\binom{k}{d}. $$ 使用二项式定理凑出 $1^{k-d}$,可以得到 $(1-1)^k=0$。 再或者,我们使用组合结论,编造一个性质 $C_n^x$ 中 $x$ 对奇数求和等于对偶数求和,可以用数学归纳法证明,或者也可以使用期望感性理解,这里不再赘述。 #### 式子 3 $$ \mu\ast\operatorname{id}=\varphi. $$ 使用 $\mu$ 的容斥意义,左边就是 $\varphi$ 的定义,在第二节中有写。 #### 式子 4 $$ f\ast\epsilon=f. $$ 比较显然,只有 $x=1$ 时 $\epsilon(x)=1$,也就是 $f(x)=f(x)\epsilon(1)=f(x)$。 以上几个式子在莫比乌斯反演中非常有用。 ## 八、莫比乌斯反演 利用莫比乌斯函数和狄利克雷卷积,往往能将复杂的结构推导至简单的式子。 ### 基础运用 请出在第二节中见面的式子,但稍作修改: $$ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]. $$ 依然使用经典技巧,得到 $$ \sum_{i=1}^{\lfloor n/k\rfloor}\sum_{j=1}^{\lfloor m/k\rfloor}[\gcd(i,j)=1]. $$ 此时内部可以视作 $\epsilon(\gcd(i,j))$。 设 $n'=\lfloor n/k\rfloor,m'=\lfloor m/k\rfloor$,原式即为 $$ \sum_{i=1}^{n'}\sum_{j=1}^{m'}\epsilon(\gcd(i,j)). $$ 应用狄利克雷卷积的 $\mu\ast I=\epsilon$,原式变为 $$ \sum_{i=1}^{n'}\sum_{j=1}^{m'}\sum_{d\mid\gcd(i,j)}\mu(d)\times1 =\sum_{i=1}^{n'}\sum_{j=1}^{m'}\sum_{d\mid\gcd(i,j)}\mu(d). $$ 交换求和符号,得到 $$ \sum_{d=1}^{\min(n',m')}\sum_{i=1}^{\lfloor n'/d\rfloor}\sum_{j=1}^{\lfloor m'/d\rfloor}\mu(d). $$ $\mu(d)$ 与 $i,j$ 无关,将其提出,得到 $$ \sum_{d=1}^{\min(n',m')}\mu(d)\left\lfloor\frac{n'}{d}\right\rfloor\left\lfloor\frac{m'}{d}\right\rfloor. $$ 此时得到的就是一个二维数论分块的形式,只需要预处理 $\mu(d)$ 的前缀和,可以在 $O(\sqrt n)$ 复杂度解决。 ### 经典 trick 考虑这个式子: $$ \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j). $$ 仍然使用经典 trick: $$ \sum_{p=1}^n\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=p]\times p. $$ 这里和第二节中不同,是我习惯在莫比乌斯反演做这一步时设成 $p$。 将 $p$ 提出,并对内部进行与上述相似操作,得到 $$ \sum_{p=1}^n p\left(\sum_{d=1}^{\lfloor n/p\rfloor}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor\right). $$ 此时括号计算的复杂度是 $O(\sqrt n)$,外层还要枚举 $n$,复杂度为 $O(n\sqrt n)$,且这个式子似乎不能再优化了……吗? 令 $T=pd$,并枚举 $T$。此时一定有 $p\mid T$,那么原式等价于 $$ \sum_{T=1}^n\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \times\left(\sum_{p\mid T}p\mu\left(\frac{T}{p}\right)\right) =\sum_{T=1}^n\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\varphi(T). $$ 预处理 $\varphi$ 的前缀和即可二维整除分块,此时时间复杂度为 $O(\sqrt n)$。 事实上,$T=pd$ 这个技巧经常被使用,往往在式子感觉推到头的时候可以起到有效作用。 ### 小结 莫比乌斯反演应用比较灵活,还是要多推一推式子才能更深刻地理解。 ## 九、杜教筛 杜教筛常常用来处理亚线性复杂度求函数前缀和的问题,写起来很像记忆化搜索。 如果想求 $f$ 的前缀和,且可以找到一个容易求前缀和的函数 $g$,且 $f\ast g$ 的前缀和也容易求得,就可以使用杜教筛。 ### 想法 设 $$ S(i)=\sum_{j=1}^i f(j). $$ 发现 $$ \begin{aligned} \sum_{i=1}^n(f\ast g)(i) &=\sum_{i=1}^n\sum_{d\mid i}f(d)g\left(\frac{i}{d}\right)\\ &=\sum_{i=1}^n\sum_{d\mid i}g(d)f\left(\frac{i}{d}\right)\\ &=\sum_{d=1}^n\sum_{i=1}^{\lfloor n/d\rfloor}g(d)f(i)\\ &=\sum_{d=1}^n g(d)\left(\sum_{i=1}^{\lfloor n/d\rfloor}f(i)\right)\\ &=\sum_{d=1}^n g(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\ &=g(1)S(n)+\sum_{d=2}^n g(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right). \end{aligned} $$ 由于 $\gcd(1,x)=1$,因此对于积性函数 $g(x)$,$g(1)g(x)=g(x)$。此时有 $g(1)=1$ 或 $g(x)=0$。不过 $g(x)=0$ 在数论中几乎没有作用,一般不考虑它。 此时也就有 $$ S(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{d=2}^n g(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right). $$ 内部是一个整除分块的形式,进行整除分块即可。 ### 时间复杂度 由数论分块的性质可以得到,当前求 $n$ 的前缀和只需要用到 $O(\sqrt n)$ 个后继节点 $v$。记这些后继节点 $v$ 形成的集合为 $\operatorname{son}$。 可以发现,后继节点的后继仍然在 $\operatorname{son}$ 中,因数的因数还是因数。因此这些后继节点只会被计算一次,因此记忆化才能保证时间复杂度正确。而一次计算是 $O(\sqrt v)$ 的,所以时间复杂度是 $$ O\left(\sum_{v\in \operatorname{son}}\sqrt v\right). $$ 有 $$ \begin{aligned} O\left(\sum_{v\in \operatorname{son}}\sqrt v\right) &=O\left(\sum_{i=2}^{\sqrt n}\left(\sqrt i+\sqrt{\frac{n}{i}}\right)\right)\\ &\le O\left(\int_1^{\sqrt n}\left(\sqrt x+\sqrt{\frac{n}{x}}\right)\,\mathrm dx\right)\\ &=O\left(n^{3/4}\right). \end{aligned} $$ 但这并不是最优。可以发现,一些可以接受线性复杂度计算的答案也要重新计算。 考虑处理了前 $B$ 个位置的前缀和,那么此时时间复杂度为 $$ O\left(B+\sum_{i\in \operatorname{son},i>B}\sqrt i\right). $$ 由于 $$ \int_1^{\sqrt n}\sqrt{\frac{n}{x}}\,\mathrm dx $$ 已经是 $n^{3/4}$ 量级,因此要求 $B>\sqrt n$。 此时复杂度就是 $$ O\left(B+\sum_{i=1}^{n/B}\sqrt \frac{n}{i}\right) =O\left(B+\int_0^{n/B}\sqrt{\frac{n}{x}}\,\mathrm dx\right) =O\left(B+\frac{n}{\sqrt B}\right). $$ 平衡一下,$B=n^{2/3}$ 时最优,复杂度也是 $O(n^{2/3})$。 ### 应用 #### 求前缀 $\varphi

取 g(x)=1,则 (f\ast g)(x)=x。

求前缀 \mu

取 g(x)=1,则 (f\ast g)(x)=[x=1]。

小结

杜教筛用来快速求前缀和,可以在很多题目中优化,需要根据 f 的特点选出合适的 g。

多项式

一、FFT 与 NTT

想法

考虑解决两个多项式相乘的问题。朴素算法需要枚举 a 的每一位,再枚举 b 的每一位,复杂度为 O(n^2)。

但可以发现,对于一个 n 次多项式函数来说,如果能够知道 n+1 个点值,那么一定可以用若干方法复原出原函数,比如朴素的高斯消元解方程或拉格朗日插值。这提示我们,对于多项式函数,其点值和多项式有着紧密联系。对于乘法这个问题,显然点值形式求解会非常简单,直接将对应点值相乘即可。

然而,仍然需要代入 O(n) 次来算点值,计算点值的复杂度也是 O(n),并没有优化复杂度。

思考是否可以通过使用某个点的答案来表示另一个点。考虑当 x^a 的指数为奇数时 (-x)^a=-x^a,当 x^a 的指数为偶数时 (-x)^a=x^a,于是自然想到通过将奇次项和偶次项分开。

形式化地说,对于函数

f(x)=\sum_{i=0}^n a_i x^i,

可以将其分为

g(x)=\sum_{i=0}^{n/2} a_{2i}x^i,\quad h(x)=\sum_{i=0}^{n/2} a_{2i+1}x^i.

此时有

f(x)=g(x^2)+xh(x^2),\quad f(-x)=g(x^2)-xh(x^2).

而 g(x) 和 h(x) 的问题和 f(x) 完全一致,于是我们可以分治然后就做完了?

你考虑这样一件事情,就是说:递归时,如果可以像 f(x) 和 f(-x) 一样,再次利用其之间的关系,就可以将需要计算的点值数量和多项式项数降低到相等的范围(即递归前规模的一半)。我们希望找到一个 x 使得传入 g 和 h 这两个函数的参数 x^2 为成对出现的相反数。显然,在实数范围内,任意不为 0 的 x 的平方都不可能为另一个 y 的平方的相反数(因为都是非负数),就没办法利用这个性质。

他山之石

数学家们定义 $i^2=-1$,这个 $i$ 就是虚数。由 $a+bi$ 形式表示的就是复数。 可以认为复数是一个平面向量,它的加减法可以和向量类比。 复数的乘法在几何上有一个精妙的表达:幅角相加,模长相乘。 #### 简单证明 类比实数乘法,可以得到 $$ (a+bi)(c+di)=(ac-bd)+(ad+bc)i. $$ 使用线性代数视角,矩阵 $$ \begin{bmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{bmatrix} $$ 等价于坐标轴顺时针旋转 $\theta$ 这一变换,也等价于向量逆时针旋转 $\theta$。 根据三角函数定义,有 $$ \cos\theta=\frac{c}{\sqrt{c^2+d^2}},\quad \sin\theta=\frac{d}{\sqrt{c^2+d^2}}. $$ 进行矩阵乘法,得到 $$ \begin{bmatrix} \frac{ac-bd}{\sqrt{c^2+d^2}}\\ \frac{bc+ad}{\sqrt{c^2+d^2}} \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} a\\ b \end{bmatrix}. $$ 数乘 $\sqrt{c^2+d^2}$ 得到 $$ \begin{bmatrix} ac-bd\\ bc+ad \end{bmatrix}, $$ 就是复数乘积的形式。 由代数基本定理可知,$n$ 次方程有 $n$ 个根,但这些根不一定都是实数。例如 $x^4=1$,不仅可以有 $x=1,-1$,也可以有 $x=i,-i$。 考虑方程 $x^n=1$,它有 $n$ 个根。由于这个方程本质相当于自己乘 $n$ 次,最后回到 $x$ 轴,联系复数乘法的几何意义可以想到将单位圆 $n$ 等分。 设“第一个”解为 $\omega_n$,那么 $\omega_n^{0\to n-1}$ 都是方程的解。 根据三角函数相关知识,可以得到 $$ \omega_n=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}. $$ 顺带一提,旋转这一形式也可以由 $e^{ix}$ 表示。有一个公式 $$ e^{ix}=\cos x+i\sin x. $$ ### 可以攻玉 复数单位根有着良好的性质。 刚才在实数范围内没有 $t'^2=-t^2$,但在复数单位根下是有的。例如在 $n=4$ 时,$i^2=-1^2$。 也就是说,若将单位根代入,那么原算法的递归过程可以继续下去。 形式化地说,单位根具有以下两个良好的性质: - $\omega_{n/2}^x=\omega_n^{2x}$; - $\omega_n^x=-\omega_n^{x+n/2}$。 为了方便递归,完全可以代入 $2^n$ 个点值,只要比多项式项数多即可。 那么递归的过程就好做了:设当前节点要代入 $n$ 个点值,将前 $n/2$ 个分别代入 $g(x^2),h(x^2)$,处理这一问题就是 $n/2$ 个点值,同时正好是 $n/2$ 次单位根。根据 $g,h$ 的答案得到 $f(x)$ 的每个答案。 ### 技巧 递归的常数还是太大了,有没有什么更快的方法? 考虑递归过程相当于从最低位开始将某一位的 $0/1$ 分开,即将奇数项和偶数项分开。 如果从下往上考虑,就会发现最底部相邻说明只有最高位不同,向上一层说明只有最高位和第二高位不同,也就是二进制位的反序。 简单理解就是,在这个过程中,低位比高位优先考虑,因此低位在比较中起关键作用。 于是考虑使用二进制的位逆序。例如: $$ x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7. $$ 一次递归变成 $$ x_0,x_2,x_4,x_6,x_1,x_3,x_5,x_7. $$ 再次递归变成 $$ x_0,x_4,x_2,x_6,x_1,x_5,x_3,x_7. $$ 可以看到,新的顺序就是将每个元素的二进制取逆序。 此时在合并的过程中,就可以从合并的角度考虑,类似倍增的过程,先考虑块长,再考虑块内每个元素的位置。设当前块长为 $2w$,那么需要利用 $i$ 和 $i+w$ 的信息进行计算,得到当前新的答案。在这个过程中可以直接覆写到数组原位置上而不影响答案。 基于以上两个优化,就可以快速求出 FFT 后的结果。此时多项式里存的其实是 $x=\omega_n^i$ 的答案。 ### IDFT 现在有了多项式的点值形式,但想要的其实是多项式形式,而不是一堆点值。 直接朴素地解方程会使复杂度出现问题;使用一些插值法难度较高且过于割裂,在复数域的操作也较为复杂。有没有什么方法可以避免这些缺点? 使用线性代数视角,相当于将一个 $n$ 维向量(系数)映射为另一个 $n$ 维向量(点值)。 使用矩阵来表达这种关系,可以想到等价于 $$ \begin{bmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & \cdots & 1\\ 1 & \omega_n^{1\times1} & \cdots & \omega_n^{1\times(n-1)}\\ \vdots & \ddots & & \vdots\\ 1 & \omega_n^{(n-1)\times1} & \cdots & \omega_n^{(n-1)\times(n-1)} \end{bmatrix} \begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{n-1} \end{bmatrix}. $$ 使用你惊人的注意力可以发现这个矩阵的逆矩阵是 $$ \frac{1}{n} \begin{bmatrix} 1 & 1 & \cdots & 1\\ 1 & \omega_n^{-1\times1} & \cdots & \omega_n^{-1\times(n-1)}\\ \vdots & \ddots & & \vdots\\ 1 & \omega_n^{-(n-1)\times1} & \cdots & \omega_n^{-(n-1)\times(n-1)} \end{bmatrix}. $$ #### 证明 设第一个矩阵为 $A$,第二个矩阵为 $B$,即证明 $AB=I$,其中 $I$ 是单位矩阵,满足 $$ I_{i,j}= \begin{cases} 1,&i=j,\\ 0,&i\ne j. \end{cases} $$ 考虑矩阵乘法的定义: $$ AB_{i,j}=\sum_{k=1}^n A_{i,k}B_{k,j}. $$ 当 $i=j$ 时,原式变为 $$ \sum_{k=1}^n \omega_n^{i\times k}\omega_n^{-k\times i}=n, $$ 每一项指数正负抵消都是 $\omega_n^0$。再乘 $\frac{1}{n}$,得到 $i=j$ 时 $A_{i,j}=1$。 当 $i\ne j$ 时,原式变为 $$ \sum_{k=1}^n \omega_n^{i\times k}\omega_n^{-k\times j} =\sum_{k=1}^n \omega_n^{(i-j)\times k}. $$ 由于 $i\ne j$,因此不妨令 $r=\omega_n^{i-j}$,此时 $r\ne 1$。应用等比数列求和得到 $$ \sum_{k=0}^{n-1}r^k=\frac{r^n-1}{r-1}. $$ $r$ 仍然是一个 $n$ 次单位根,因此 $r^n-1=0$。 所以 $AB=I$,即 $A^{-1}=B$。 于是逆变换完全可以将单位根的倒数代入 FFT,并在最后计算答案时除以 $n$,就能起到 FFT 逆变换的作用。 ### NTT FFT 过程中要用到大量的浮点数运算,从效率上、精度上都不是一个很优秀的选择。有没有什么办法能够避免这些问题? 在数论第五节中有提到:“原根有着和复数单位根相似的性质”。它们都是自己乘若干次之后回到 $1$,并且在过程中互不相同。 严格地说,FFT 的过程只用到了这两个性质: - $\omega_{n/2}^x=\omega_n^{2x}$; - $\omega_n^x=-\omega_n^{x+n/2}$。 对应到原根,也需要让其满足这个性质。 首先假设 $n\mid\varphi(m)$。 不妨取 $$ \omega_n=g^{\frac{\varphi(m)}{n}}, $$ 其中 $g$ 是原根。那么上述两个性质都满足。 #### 性质 1 $$ \omega_{n/2}^x =g^{\frac{\varphi(m)}{n/2}x} =g^{\frac{\varphi(m)}{n}\times2x} =\omega_n^{2x}. $$ #### 性质 2 本质在证 $$ g^{\frac{\varphi(m)}{2}}\equiv -1\pmod m. $$ 设原式为 $x$,则有 $x^2\equiv 1\pmod m$,即 $x\equiv\pm1\pmod m$。 若 $x\equiv 1\pmod m$,则说明 $\frac{\varphi(m)}{2}$ 是一个阶,与原根定义矛盾。 于是可以将 FFT 中的复数单位根用原根替代。但考虑到需要尽可能让 $\varphi(m)$ 简单,并且 $\varphi(m)$ 尽可能整除 $2^x$,让 $x$ 尽可能大。 $998244353$ 就是一个很好的 NTT 模数,因为它是一个质数,且 $2^{23}\mid 998244352$。最小原根也只有 $3$。特别地,$114514$ 也是 $998244353$ 的一个原根。 ## 二、多项式求逆 ### 定义 设 $a,b$ 是两个多项式,若 $ab=1$,则称 $b$ 是 $a$ 的逆,习惯上记作 $a^{-1}$。 但是,我们发现,有些函数的逆没有办法精确表达,需要无穷项,比如 $1-x$ 的逆,我们发现 $(1+x+x^2)(1-x) = 1-x^3, (1+x+x^2+x^3)(1-x)=1-x^4$,这个乘积永远跟 $1$ 有着误差项,而且误差项的次数越来越高。 出于现实需求/效率的考虑,我们往往不需要精确到无穷多位,很多时候我们只需要截取后 $n$ 位作为运算结果就足够表示新的多项式。 在本文中用 $a \bmod x^n$ 表示“截取” $a$ 的 $x^{0 \to n-1}$ 项,并将 $x^n$ 以上的项忽略的多项式。 那么本节要讨论的问题就是,给定 $a$,求出 $b$ 满足 $ab\equiv 1\pmod{x^n}$。 ### $O(n^2)$ 递推 根据多项式乘法定义 $ab_i = \sum_{j=0} a_jb_{i-j}$,且 $ab=1$,可以得到如下结论: - $a_0b_0 = 1$,即 $b_0 = a_0^{-1}$。 - $\sum_{j=0}^i a_jb_{i-j}$,展开后移项可以得到 $b_i = -\frac{1}{a_0}\sum_{j=0}^{i-1} b_ja_{i-j}$。 因此,我们可以通过前 $i-1$ 位的系数计算出第 $i$ 位的系数,递推 $n$ 项时间复杂度 $O(n^2)$。 ### 牛顿迭代法 $O(n\log n)

假设我们已经求出 ab_0 \equiv 1 \pmod{x^w},希望将其扩展为 ab \equiv 1 \pmod{x^{2w}}。

左右同时平方,得到 $b^2 - 2bb_0 + b_0^2 \equiv 0 \pmod{2w}$,移项得到 $b^2 \equiv 2bb_0 - b_0^2 \pmod{2w}$。 左右同时乘 $a$,在 $\bmod x^{2w}$ 意义下 $ab=1$,因此有 $b \equiv (2 - b_0a)b_0 \pmod{2w}$。 此时我们就得出了 $\bmod x^{2w}$ 意义下的 $a^{-1}$,重复迭代直到精度超过我们要求的 $n$ 为止。 #### 时间复杂度 每次迭代需要乘法,设当前长度为 $w$ 则当前迭代复杂度为 $w \log w$。 由于 $\log w < \log n$,因此 $\sum w \log w < \sum w \log n = (\sum w) \log n$,前面的求和得到 $\sum w = O(n)$,因此总复杂度 $O(n \log n)$。 ## 三、多项式除法 ### 定义 给定 $n$ 次多项式 $a$,$m$ 次多项式 $b$,求出 $n-m$ 次多项式 $q$ 和低于 $m-1$ 次多项式 $r$,满足 $a=bq+r$。 ### 思路 一个直接的想法是,对 $b$ 求逆,然后计算 $ab^{-1}$ 得到 $q$。 但这样,你的误差项在高次而不是低 $m-1$ 次。 为了让 $r$ 出现在高次项,我们可以使用翻转技巧。 左右同乘 $x^n$,并另 $x = \frac{1}{x}$,此时第 $i$ 项就是 $x^{n-i}$,我们发现这正好是多项式的系数反转,记这个操作后的多项式为 $f^R$。 此时仍然有 $a^R = b^Rq^R + x^{n-m+1}r^R$,此时余项 $r$ 被放到了高位,在 $\bmod x^{n-m+1}$ 意义下可以直接舍去。 此时可以直接使用 $q^R \equiv a^R(b^R)^{-1} \pmod{x^{n-m+1}}$,最后再反转 $q^R$ 得到 $q$。 由 $a=bq+r$,可以直接通过 $a-bq$ 算出 $r$。 ### 时间复杂度 只用到了 $O(1)$ 次乘法和 $O(1)$ 次多项式求逆,复杂度 $O(n \log n)$。 ## 四、多项式求导与积分 ### 求导 考虑两个点 $(x, f(x)), (x+\delta, f(x+\delta))$,如果我们连接这两个点,可以在一定程度上反映这段区间的变化率,即 $\frac{f(x+\delta) - f(x)}{\delta}$。 考虑当 $\delta$ 无限接近 $0$,此时这段区间的变化率就是 $x$ 这一点上的变化率。 形式化地,定义 $f'(x)=\lim_{\delta\to 0} \frac{f(x+\delta) - f(x)}{\delta}$,其中 $\lim$ 表示极限,就是让 $\delta$ 无限趋近于 $0$。这里如果要严谨的定义较为复杂,且与 OI 关系不大,这里不再展开,感兴趣的读者可以自行了解。 也就是说,导数反映的是当前位置的变化率,也可以认为是当前位置切线的斜率。 ### 常见函数求导 1. $(f(x) \pm g(x))' = f'(x) \pm g'(x)
  1. (f(x)g(x))' = f(x)g'(x) + f'(x)g(x)
  2. (f(g(x)))' = f'(g(x))g'(x)
  3. (x^n)' = nx^{n-1}
  4. (e^x)' = e^x
  5. (\ln x)' = \frac{1}{x}
  6. (\sin x)' = \cos x
  7. (\cos x)' = -\sin x

证明对 OI 的启发意义不大,感兴趣的读者可以自行代入定义证明。

积分

求导的逆运算,有牛顿-莱布尼茨定理:

于是上述求导都可以左右同时积分得到积分的关系式。 在多项式中,求导和积分是易于实现的: - $n$ 次多项式求导之后变成 $n-1$ 次多项式且 $i-1$ 次项系数等于原多项式 $i$ 次项乘 $i$。 - $n$ 次多项式积分之后变成 $n+1$ 次多项式且 $i$ 次项系数等于原多项式 $i-1$ 次项除以 $i$。 ## 五、多项式 $\ln

泰勒展开

泰勒展开简单来说就是通过多项式拟合一个函数,他的定义是:

g(x) = \sum_{i=0}^{\infty} \frac{x^i}{i!} f^{(i)}(0).

感性理解,如果一个函数在 x=0 处函数值与变化率与原函数相同,变化率的变化率与原函数相同,变化率的变化率的变化率相同 \dots,那么二者在 x=0 处越来越相似。因此将函数构造一个多项式使得它的系数与 f^{(i)}(0) 相同,再积分就得到了这个多项式的拟合。不过这样忽略了常数项,于是我们需要常数项满足 c = g(0) = f(0)。

代入公式可以得到以下结论

定义

取 \ln 的泰勒展开意义,由于多项式下模意义下不能很好地处理实数,为了方便,我们要求 f 的常数项为 1。

令 g(x) = f(x) - 1,带入泰勒展开即可得到 x - \frac{g(x)^2}{2} + \frac{g(x)^3}{3} - \dots,于是我们得到了多项式 \ln 的表达式。

快速求解多项式 \ln

使用第四节中我们提到过的公式:

代入求解 (\ln(f(x)))' 可以得到 (\ln(f(x)))' = \frac{1}{f(x)}f'(x)。

左右同时积分,可以得到 \ln(f(x)) = \int \frac{1}{f(x)}f'(x) dx。

此时我们只需要进行一次多项式求逆,一次多项式求导,一次多项式乘法,一次多项式积分就能够得到 \ln(f(x))。

时间复杂度

上述所有运算都可以 O(\log n) 或 O(n) 快速求出,故整体 O(n \log n)。

六、多项式 \exp

前文提到 e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots。由于 e^0=1,为了方便,我们要求 f 的常数项为 0。

快速求解多项式 \exp

仍然使用牛顿迭代法:

由于 e^0=1,因此 \exp f(x) 的常数项为 1。

设 g(x) = \exp f(x),h_0(x) \equiv \exp f(x) \pmod{x^w}。

我们希望将其扩展为 h(x) \equiv \exp f(x) \pmod{x^{2w}},设当前误差为 \epsilon,即 h_0(x) = g(x)(1 + \epsilon),且 \epsilon 是一个最低次数为 n 的多项式。

左右同时取 \ln 得到 \ln g(x) = \ln h_0(x) + \ln (1 + \epsilon)。

代入 \ln(1 + \epsilon) 的泰勒展开式得到 \ln(1 + \epsilon) = \epsilon - \frac{\epsilon^2}{2} + \frac{\epsilon^3}{3} - \dots,在 \bmod (x^{2w}) 意义下后面高次项可以省略,因此 \ln(1 + \epsilon) \equiv \epsilon \pmod{2w}。

于是我们得到 \epsilon \equiv \ln h_0(x) - \ln h(x) \pmod{2w},由于 g(x) = \exp f(x),因此 f(x) = \ln g(x),

由于 \frac{1}{1 + \epsilon} = 1 - \epsilon - \epsilon^2 - \dots,在 \bmod x^{2w} 意义下后面高次项省略得到 1 - \epsilon。

于是 h(x) = h_0(x)(1 - \ln h_0(x) + f(x))。

时间复杂度

与第二节的分析类似,所有操作的复杂度都为 O(n \log n),总复杂度 O(n \log n)。

应用

多项式快速幂

由于 x^k = e^{k \ln x},于是一次 \ln 一次 \exp 即可。

多项式开根

把上述 k 改为 \frac{1}{2} 即可。

小结

多项式运算是一类工具性的运算,在未来的生成函数中运用得较为广泛,且这些运算往往涵盖着一系列组合意义(这就是另一个话题了)。

组合数学

一、错排

定义 D(x) 表示 x 个数形成的排列 P 中对于任意 i 满足 P_i \ne i 的数量。

考虑递推,定义 D(0)=1, D(1)=0。

对于新加入的 i,由于他不能加入在 i 的位置上,因此必然在 1 \to i-1 的一个位置将原数改为自己,分类讨论这个被占掉位置的数:

选择交换的对象共有 (i-1) 个,因此方案数要乘 (i-1),因此有 D(i) = (i-1)(D(i-1) + D(i-2))。

二、容斥原理

引入

有时候,我们可以希望计数,但这些答案往往直接计算会算重或算漏,比如:

这些问题往往直接求解难以计算,但往往有一些比较容易计算的,但会算多/重的答案。比如:总人数可以先将喜欢数学和喜欢物理的学生直接加起来,但会将二者都喜欢的学生算两遍。

形式化地说,我们要求解的问题形如求满足几个条件的并集或者进一步根据集合之间的关系求出某些部分。

想法

容易想到,当集合数量为 2 时,我们可以直接将两个集合的大小相加,再减去“被算重的部分”,也就是两个集合的交集。但当有三个集合时,如果仅两两将交集减去,那么我们会发现三个集合共有的部分被集合大小为 1 的集合算了 3 次,被集合大小为 2 的集合算了 -3 次,而实际上只应该被算一次,所以要在加上大小为 3 的集合的贡献(这里画维恩图可能效果更好)。

然而,当 n 逐渐增大,我们不可能逐项计算每个集合大小对应的贡献,但根据上面的三项式子,我们已经有所发现:集合大小为奇数的项贡献为 1,偶数大小的项为 -1。

证明

在数论第七节中,我们口胡了一个性质 \sum_{x=0}^n (-1)^xC_n^x = 0,这里详细证明一下。

从组合意义上看,我们发现问题其实就是证明从 n 选奇数的方案数和 n 选偶数的方案数相等。

  1. 奇数项:展开可以得到 \sum_{i=0}^{\frac{n}{2}} C_{n-1}^{2i} + C_{n-1}^{2i + 1},我们发现这就是上一行的组合数总和。
  2. 偶数项:与奇数项相似,如果我们认为 m<0 或 m>n 时 C_n^m = 0 直接套用上面的式子容易得到也是上一行的总和。

另一种证明要用到后面会讲到的二项式定理,给每一项凑一个 1^{n-x},直接代入二项式定理公式得到 (1-1)^n=0。

借助这个式子,我们可以进行一些计算:

形式化地表述,有

\left|\bigcup S_i\right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \le a_1 < a_2 < \dots < a_{k-1} < a_k} \left|\bigcap_{i=1}^k S_i\right|.

上述式子也可以借助数论第二节的单点求 \varphi 理解,或者正如前文所说,单点求 \varphi 也相当于对质因数容斥并展开成因式分解形式。

练习

考虑容斥,问题转化为求盒子不为空的并集,按照前文容斥:

计算得到 240。

如果把盒子视作相同的,上述答案只需要除以盒子的排列 4!,这也是著名的“斯特林数”。

前两个例题不写了,读者有兴趣可以自行做一做。注意:第二问中如果你直接容斥要注意,一个数能既被 a 整除又被 b 整除,不意味着一定被 ab 整除。

这里引入一个更有趣的东西:用容斥的方法求错排。

问题等价于求每个元素不再自己位置上的并集,考虑至少 x 个元素位置正确,即先选 x 个元素,剩下随意排列,也就是

\sum_{i=0}^n (-1)^i\times C_n^i\times (n-i)!,

我们得到了另一种错排公式且不需要递推。

三、卡特兰数/反射容斥

定义

容易知道,一个点起始位置为 (0,0),每次可以从 (x,y) 走到 (x+1,y) 或 (x,y+1),走 2n 步到 (n,n) 的方案数为 C_{2n}^n。(组合意义,选取 n 步向上 n 步向右)

那如果加一条限制:在过程中经过的点不允许出现 y>x。形象地说,不允许越过 y=x 这条直线,但可以经过。直接组合数学不太方便,我们记走到 (n,n) 的方案数为卡特兰数 C_n。

另一种数列的表达方法是,设卡特兰数第 n 项为 C_n,则有

C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1},

初始有 C_0=1。

这两种定义方法是等价的。

原因在于,考虑第一次走到 y=x 这条直线上的点 (k,k)。可以发现,从 (0,0) 出发的点一定向右(向上到 (0,1) 了),(k,k) 这个点一定是由下方 (k,k-1) 走过来(向左到 k-1,k 了)。

由于 k 是第一个与 y=x 的交点,因此从 (0,1) 到 (k,k-1) 一定不交于 y=x,也一定不越过 y=x-1。向左平移 1 个单位长度,与原问题等价,即从 (0,0) 走到 (k-1,k-1),而从 (k,k) 走到 (n,n) 的方案等价于从 (0,0) 走到 (n-k,n-k)。于是原问题等价于 a_n = \sum_{i=1}^n a_{i-1}a_{n-i},正是卡特兰数的定义。

应用

卡特兰数的用途比较多,原因在于以上两种定义在各种结构中都比较常见,比如:

诸如此类,有明显的 a 不大于 b 或将问题划分为两个子问题往往与卡特兰数有关。

公式

上面的递推式子是 O(n^2) 的,但事实上有更快的计算方法。

有通项公式

C_n = C_{2n}^n - C_{2n}^{n-1},\quad C_n = \frac{C_{2n}^n}{n+1},

递推公式

C_n = \frac{4n-2}{n+1}C_{n-1}.

这里只证明第一个式子,后两个式子可以由它展开推导而来。

证明

考虑使用直线的定义方式,观察式子可以想到应该是用总方案数减去不合法的方案数。

现在唯一问题就是如何刻画这个“越过 y=x”的性质。

考虑取第一次越过 y=x 的位置,它必然是一个 (x,x+1) 的形式,将这个点后面的部分沿 y=x+1 翻折,或者说,将向右变为向上,向上变为向右,这时我们发现翻折后 (n,n) 点变为了 (n-1, n+1)。

另一种视角是,我们将向右与向上互换,而我们知道当前位置在 (x,x+1),也就是已经走了 x 步向右,x+1 步向上。还剩 n-x 步向右,n-x-1 步向上。交换之后等价于向右走了 n-1 步,向上走了 n+1 步。

这种证明方法也被称之为反射容斥,对于一些问题,找到一些容斥方法,并对不好计算的问题使用一些方法找到与其双射且容易计数的问题,在这里是利用 y=x+1 “反射”到对面因此称为反射容斥。

四、二项式定理

若 a,b 对 \times 有交换律,对 + \times 有结合律,则有

(a+b)^n=\sum_{i=0}^n a^i\times b^{n-i}\times C_n^i.

简单使用组合意义,有 n 个元组 a,b。a^i 项相当于从 n 个 a 中选取 i 个,剩下 n-i 个选择 b,该项一共贡献 C_n^i。

trick

比较经典的是用 1 来配凑二项式定理的形式,在本文数论第七节和本章第二节中都出现了这个式子。

比如:

\begin{aligned} \sum_{i=1}^n \sum_{j=0}^{now-1}C_{now-1}^i \times 2^{i-j-1} = \sum_{i=1}^n\sum_{j=0}^{now-1}C_{now-1}^i \times 2^{i-j-1}\times1^j \end{aligned}

其中 now 是一个变量,随 i 变化,直接计算最坏 O(n^2)。

这个式子这与二项式定理非常相似,但 2 的指数与求和上界不同,但考虑到 i 与 j 无关,不妨将 2^{i-now+1} 提出,内部变为 2^{now-1},运用二项式定理得到

ans=\sum_{i=1}^n 2^{i-now+1}\times3^{now-1}.

可以 O(n) 或 O(n \log n) 计算。

另一种 trick 是,有时我们只希望求出二项式奇数/偶数项的和,要求在 O(\log n) 复杂度内解决。

例如:

\sum_{i=0}^{\frac{n}{2}} C_n^{2i} a^{2i} b^{n-2i}

这个式子长得和二项式定理十分相似,唯一的不同就是他没有奇次项。

考虑怎么把奇次项消掉,你考虑到 (-1)^k 正好可以做到 k 是奇数时 (-1)^k = -1,k 是偶数时 (-1)^k=1。

于是配凑一个 (a-b)^n,我们发现

(a+b)^n + (a-b)^n = 2 \times ans.

于是我们可以使用快速幂 O(\log n) 处理。

五、范德蒙德卷积

定义

狭义地说,卷积是两个函数之间的关系,即 h(x) = \sum_{i=0}^x f(i)g(x-i)。但在这里和之前数论第七节的“狄利克雷卷积”一样,描述的更像是两个对象互相之间存在某种联系,并在计算形式上与卷积高度相似。

具体地讲,范德蒙德卷积形如

C_{n+m}^k = \sum_{i=0}^k C_n^iC_m^{k-i},

利用这个式子我们可以将一些看起来复杂的组合乘积变得简洁。

证明

使用二项式定理,考虑到多项式乘法就有着这种卷积的形式,于是考虑构造 (1+x)^k。

取 (1+x)^n, (1+x)^m,二者相乘得到 (1+x)^n\times (1+x)^m = (1+x)^{n+m},设系数序列分别为 a,b,c。

直接展开,根据多项式乘法的定义,我们有 c_{i+j} = \sum_i\sum_j a_ib_j,等价于 c_k = \sum_{i=0}^k a_ib_{k-i}。

根据二项式定理,可以知道 a_i = C_n^i, b_i = C_m^i, c_i = C_{n+m}^i,代入到上式中自然得证。

使用组合意义证明:C_n^i 代表从 n 中选 i 个,C_m^{k-i} 代表从 m 中选 k-i 个。可以想象将 n+m 分为 n 和 m。枚举 i 实质上是在列举所有在两类中共选取 k 个的所有方案,也就是 C_{n+m}^k。

应用

利用范德蒙德卷积可以得出一些简洁的恒等式:

都比较容易证明,这里只证明第二个式子,其他类似证明即可。

我们知道 C_n^i = C_n^{n-i},于是原式等价于 \sum_{i=0}^n C_n^iC_n^{n-i},这就是范德蒙德卷积的形式,代入公式得到 C_{2n}^n。

六、二项式反演

定义

若

f(i) = \sum_{j=0}^i C_i^j g(j),

则有

g(i) = \sum_{j=0}^i (-1)^{i-j}C_i^j f(j).

另一种表达方式是

f(i) = \sum_{j=i}^N C_j^i g(j),

则有

g(i) = \sum_{j=i}^N (-1)^{j-i}C_j^i f(j).

这个式子十分对称,左右结构相似,只差了一个 (-1)^{i-j} 的系数。

证明

这个式子看起来长得就很像容斥,通过容斥视角可以很好的理解这个式子。

我们把 f(i) 视作“至少/钦定 i 个元素符合条件”的方案数,g(i) 视作“恰好有 i 个元素符合条件”的方案数。比如在错排中,我们记“至少有 i”个元素位置正确的方案数为 f(i),恰好有 i 个元素位置正确的方案数为 g(i)。此时对于一个 f(i),他会被 j\ge i 的 g(j) 贡献 C_j^i 次。(从 j 中选 i 个,任意一个都会给 f(i) 贡献)。也就是

f(i) = \sum_{j=i}^n g(j)C_j^i.

我们发现,上述例子中 f(i) 容易计算,只需先钦定 i 个元素正确再让剩下的 n-i 个元素随便排列,但 g(i) 并不好算,于是考虑容斥。

对于 g(i) 我们首先想到直接用 f(i) 来计算它,但这样就算上了 C_{i+1}^{i} g(i+1), C_{i+2}^i g(i+2) \dots。而事实上我们希望这些项的贡献为 0,因此对于 g(i+1) 的贡献我们要减去,也就是 -C_{i+1}^i f(i+1),但这样又影响了后面的贡献,i 和 i + 1 对 i + 2 产生了 C_{i+2}^i-C_{i+2}^{i+1}C_{i+1}^i 的贡献,展开计算可以得到

\frac{(i + 2)(i+1)}{2} - (i+2)(i+1) = -\frac{(i+2)(i+1)}{2} = -C_{i+2}^i

的贡献,于是要加上 C_{i+2}^i g(i+2) 的贡献。

当我们算到第 j 项,设 j-i=A,此时第 j 项的贡献就是

\sum_{k=0}^{A-1} C_{j}^{i+k}C_{i+k}^{i}(-1)^k

(第 j 项的系数为 (-1)^{j-i} C_{i+k}^{i},f(i+k) 向 f(j) 贡献了 C_{j}^{i+k})。

这里需要引入一个组合恒等式 C_a^bC_b^c = C_a^cC_{a-c}^{b-c}。组合意义上,从 a 中选 b 个,在从 b 中选 c 个相当于分为三类,分别由 a-b, b-c, c 个。可以改变分的顺序,先在 a 中选 c 个,再从 a-c 中选 b-c 个。

利用这个等式,可以得到

\sum_{k=0}^{A-1} C_{j}^{i+k}C_{i+k}^{i}(-1)^k = \sum_{k=0}^{A-1} C_j^iC_{j-i}^k(-1)^k = C_j^i\left(\sum_{k=0}^{A-1} C_A^k (-1)^k\right),

而我们在第二节证明了 \sum_{x=0}^n (-1)^xC_n^x = 0。那么取当前项系数为 C_j^iC_A^A(-1)^A 即有 C_j^i(\sum_{k=0}^A C_A^k (-1)^k)=0,而 C_A^A=1,因此,C_j^i(-1)^A=C_j^i(-1)^{j-i} 就是第 j 项的系数。

因此有

g(i) = \sum_{j=i}^n C_j^if(j)(-1)^{j-i}

成立。

对于我们先前举的那个例子,错排问题等价于 g(0)。代入

g(0) = \sum_{j=0}^n f(j)(-1)^j,

与我们之前的推论一致。

小结

二项式反演往往能够解决“钦定/至少”容易计算而“恰好”较难计算。如果能够找到这样的关系,就可以利用二项式反演解决问题。

博弈论

一、基本定义

“博弈”在许多语境中被表达为为谋取利益而竞争。这个定义并不完全是数学上的博弈论,但这个定义至少说明了几个关键点:

  1. 争夺利益,双方会尽可能使结果对自己有利。
  2. 竞争,这意味着博弈往往是双方或多方的行为。

在这里我们定义“博弈”的意思是:在一定条件下,遵守一定的规则,一个或几个拥有绝对理性思维的人或团队,从各自允许选择的行为或策略进行选择并加以实施,并从中各自取得相应结果或收益的过程。(from 百度百科)。

也就是说,双方绝对聪明,且一定会选择对自己有利的结果,本章中所有内容基于这个前提下讨论。

一些记号与约定

在本章中会出现以下几个名词和记号:

二、sg 函数

定义

sg 函数的定义是

\operatorname{sg}(x) = \operatorname{mex}_{v \in \operatorname{son}(x)} \operatorname{sg}(v),

一般有 \operatorname{sg}(0) = 0。

比如经典的 nim 博弈,有 \operatorname{sg}(x)=x。

对于单个博弈,如果 \operatorname{sg}(x) 不为 0 那么先手必胜,否则后手必胜。

对于多个独立的博弈,它的胜负状态就是所有博弈的 sg 异或和。

为什么是这样

就是说你去考虑这样两件事情:

如果能证明这两个,那么异或和是否为 0,就等价于博弈中的必胜和必败(必胜只要转化到一个必败就行,必败无法转移到另一个必败)。

由于 sg 函数的定义是 \operatorname{mex}_{v \in \operatorname{son}(x)} \operatorname{sg}(v),因此对于任意操作,都不可能有 \operatorname{sg}(v) = \operatorname{sg}(x)。那么 \operatorname{sg}(x) \oplus \operatorname{sg}(v) \ne 0,第一部分就证完了。

再考虑第二部分,由于异或和不为 0,我们去考虑最高位是 1 的位置。必然存在一个数,他的最高位为 1。此时除了这个数以外的数的异或和最高位就变成 0 了(更高位本来就是 0, 0 \oplus 0 = 0,当前位置本来是 1 但 1 \oplus 1 = 0。此时除了这个数以外的数的异或和最高位就变成 0。

此时由于 \operatorname{sg}(x) 的当前位为 1 而剩余 sg 的异或当前位为 0。因此 \operatorname{sg}(x) 大于剩下的异或(比较大小从高向低考虑)。

根据 \operatorname{mex} 的定义,我们知道,任何更小的值一定存在与 x 的后继状态中,所以转移到这个状态之后,全局异或和为 0(x \oplus x = 0)。

于是以上两个性质都成立,可以等价与博弈中的必胜状态与必败状态。

题单

推荐题单制作者写的博客,讲得也非常好。

AI 使用说明

本文在排版与文字润色过程中使用了 DeepSeek 辅助,主要用于 Markdown 排版、标点与空格规范检查、LaTeX 公式格式整理以及明显笔误修正。文章中的数学内容、算法结论与证明思路由作者负责。

update

本篇博客带有一些学习笔记的性质,主要是笔者曾经/近期学过的较为重要/有趣的数学算法。

有趣的是,虽然本篇博客叫做“从入门到入土”,但部分读者认为本篇博客不够入门,部分读者认为不够入土。

如果本文有什么问题或者有什么意见,欢迎指出。