数学一家子

主要还是组合数学之类的，数论考的比较少写的也比较少。

0. 排列组合

定义 $A _ {m} ^ n$ 表示从 $m$ 个物品中有序地取 $n$ 个，发现第 $i$ 次有 $m - i + 1$ 种选择，则 $A _ {m} ^ n = \prod \limits _ {i = 1} ^ n (m - i + 1) = \frac{m!}{(m - n)!}$ ；定义 $C _ m ^ n$ 表示从 $m$ 个物品中无序地取 $n$ 个，与上面的区别是每个互不区分，所以有 $C _ m ^ n = \frac{A _ m ^ n}{n!} = \frac{m!}{n!(m - n)!}$ 。

还有就是两个原理，一个问题可以被分成几个互相独立的子问题，则问题的答案是所有子问题的答案之和，称为加法原理；如果这几个子问题不独立，则答案为几个子问题的答案之积，称为乘法原理。

卡特兰数

问就是考到了不会。

定义式是这样的： $C _ n = \begin{cases} 1,n = 0 \\ \sum \limits _ {i = 0} ^ {n - 1} C _ i C _ {n - i - 1}, n \gt 0 \end{cases}$ 。因此，卡特兰数和规模为 $n$ 的可以通过枚举分界点而分成 $i$ 与 $n - 1 - i$ 的子问题的问题关系密切。

一个经典的例子是对于一个 $n \times n$ 的网格图，左下角为 $(0,0)$ ，右上角为 $(n,n)$ 从左下角开始每次只能向右或向上走一格，不能越过直线 $y = x$ 的方案数为 $C _ n$ 。

证明一下，设 $F _ k$ 表示从 $(0,0)$ 到 $(k,k)$ 的合法路径数，则第一步一定向右走到 $(1,0)$ ，最后一步一定是从 $(k,k - 1)$ 走到 $(k,k)$ ，上述方案数为 $F _ {k - 1}$ 。而从 $(k,k)$ 走到 $(n,n)$ 的方案数为 $F _ {n - k}$ ，这个 $k$ 的贡献就是 $F_ {k - 1} F _ {n - k}$ 。所以， $F _ n = \sum \limits _ {k = 1} ^ n F _ {k - 1} F _ {n - k}$ ，令 $i = k + 1$ 则有 $F _ {n} = \sum \limits _ {i = 0} ^ {n - 1} F _ i F _ {n - 1 - i}$ ，恰好是卡特兰数的递推式。

更一般的，我们可以抽象上面的模型成：有两种操作，在任何时候第二种操作的次数不得少于第一种操作的次数，求长度为 $n$ 的合法操作序列方案数。

符合上面模型的就有很多了，比如括号序列计数与出栈序列计数等。

但是，类卷积式还是算的太慢了，以下是几个可以 $\Omicron(n)$ 计算的式子：

C _ {n} = \frac{1}{n + 1}C _ {2n} ^ n = \frac{(2n)!}{n!(n + 1)!} \\ C _ {n} = C _ {2n} ^ n - C _ {2n} ^ {n + 1} \\ C _ {n} = \frac{4n - 2}{n + 1} C _ {n - 1}

1. 欧拉函数

定义为 $\varphi(x) = \sum \limits _ {i = 1} ^ {x} [\gcd(i,x) = 1]$ 。是个积性函数。

对于单个函数的计算可以用 $\varphi(n) = n \prod \limits _ {i = 1} ^ k \frac{p _ i - 1}{p _ i}$ 来算，其中 $n = \prod \limits _ {i = 1} ^ k {p _ i} ^ {a _ i}$ 。多个的计算可以直接线性筛，显然有 $\varphi(p) = p - 1,p \in \text{Primes}$ ，整除那里的特判是 $\varphi(i \times p) = \varphi(i) \times p$ ，感性理解一下就是因为乘的是个质数所以 $\varphi(i)$ 的每一种互质情况都可以在 $\varphi(i \times p)$ 中体现，而 $[1,p - 1]$ 中每一个数都与 $p$ 互质，所以 $(i(j - 1),ij]$ 中的每个原本互质的数仍然互质，所以是 $\varphi(i \times p) = \varphi(i) \times p$ 。

有个结论是 $n = \sum \limits _ {d \mid n} \varphi(d)$ ，可以拿来化简式子，狄利克雷卷积的形式是 $\mathbf{Id} = \varphi \ast \mathbf{1}$ ，在杜教筛里面有用。

欧拉定理

若有 $\gcd(a,p) = 1$ ，则有 $a ^ {\varphi(p)} \equiv 1 \pmod p$ 。

这个的应用范围还是有点太小了，所以有扩展欧拉定理： $a ^ p \bmod m = \begin{cases} a ^ {p \bmod \varphi(m)} & \gcd(a,m) = 1 \\ a ^ p & \gcd(a,m) \neq 1 \wedge p \lt \varphi(m) \\ a ^ {p \bmod \varphi(m) + \varphi(m)} & \gcd(a,m) \neq 1 \wedge p \ge \varphi(m) \end{cases} \bmod m$ 。

欧拉函数有个性质， $\varphi(\varphi(n)) \leq \frac{n}{2}$ ，因为对于一个奇数，一定有 $\varphi(n) = n \prod \frac{2k}{2l + 1}$ ，所以一定会变成偶数，而对于一个偶数，小于它的偶数一定不与它互质，这一部分有 $\frac{n}{2}$ 个，所以 $\varphi(\varphi(n))$ 一定小于等于 $\frac{n}{2}$ 。

依据这个，我们可以解决一类模意义下的幂塔求值问题。因为模数会在 $\Omicron(\log n)$ 次操作后变为 $1$ 。

模板可以看看 Codeforces 906D↗。

2. 容斥

一句话就是 $|S _ 1 \cup S _ 2 \cup \ldots \cup S _ n| = \sum \limits _ {k} (-1) ^ {k - 1} |\bigcap \limits _ {1 \le p _ 1 \lt p _ 2 \lt \ldots \lt p _ k \le n} S _ {p _ i} |$ 。

在数数题里面拿来去重。

二项式反演

二项式定理众所周知了提一嘴就行： $(x + y) ^ n = \sum \limits _ {i = 0} ^ n C _ n ^ i x ^ i y ^ {n - i}$

由于这是总结所以我懒得写证明了，设 $f(x)$ 为至少 / 至多 $x$ 的方案数， $g(x)$ 为恰好 $x$ 的方案数：

则有：

至少的情况： $f(n) = \sum \limits _ {i = n} ^ m C _ m ^ n g(i) \Leftrightarrow g(n) = \sum \limits _ {i = n} ^ m (-1) ^ {i - k} C _ m ^ n f(i)$
至多的情况： $f(n) = \sum \limits _ {i = 0} ^ n C _ n ^ i g(i) \Leftrightarrow g(n) = \sum \limits _ {i = 0} ^ n (-1) ^ {n - i} C _ n ^ i f(i)$

3. 大大小小的数论定理

Bezout 定理

设 $a,b$ 为不全为 $0$ 的整数，则 $\forall x,y \in \Z,\gcd(a,b) \mid ax + by$ ，并且 $\exist x,y \in Z,ax + by = \gcd(a,b)$ 。

下面几个都有普通和 ex 版本。

辗转相除法

$\gcd(x,y) = \gcd(y,x \bmod y)$ ，当 $y = 0$ 时为 $x$ 。

exGCD

用来解 $ax + by = \gcd(a,b)$ 的一组特殊解。

这个可以顺手求 $\gcd(a,b)$ ，到最底层 $x _ n = 1,y _ n = 0$ ，之后每一层有 $x _ n = y _ {n + 1}，y _ n = x _ {n + 1} - \lfloor \frac{a}{b} \rfloor y _ {n + 1}$ 。

CRT

哎我感觉不如下面的 exCRT 好用。

求解的是如下一元线性同余方程组： $\begin{cases} x \equiv a _ 1 \pmod {n _ 1} \\ x \equiv a _ 2 \pmod {{n _ 2}} \\ \vdots \\ x \equiv a _ k \pmod {n _ k}\end{cases}$ ，条件是所有 $n _ i$ 两两互质。

做法如下：

求出 $N = \prod n _ i$
对于第 $i$ 个方程，求出 $m _ i = \frac{N}{n _ i}$ 与 $m _ i$ 在模 $n _ i$ 意义下的逆元 $m _ i ^ {-1}$ ，最后答案为 $\sum a _ i m _ i m _ i ^ {-1} \pmod N$ 。

exCRT

轮椅。

条件是删去 CRT 的条件，在某些题里面可以用来合并答案。

设有两个方程 $x \equiv a _ 1 \pmod {n _ 1},x \equiv a _ 2 \pmod {n _ 2}$ 。

则可以转化为不定方程 $x = k _ 1 n _ 1 + a _ 1,x = k _ 2 n _ 2 + a _ 2$ ，则有 $k _ 1 n _ 1 - k _ 2 n _ 2 = a _ 2 - a _ 1$ 。

由 Bezout 定理，当 $\gcd(n _ 1,n _ 2) \nmid a _ 2 - a _ 1$ 时无解。

否则可以用 exGCD 求出来一组可行的 $k _ 1,k _ 2$ ，两原方程可以合并为 $x \equiv k _ 1 n _ 1 + a _ 1 \pmod {\operatorname{lcm}(n _ 1,n _ 2)}$ 。

合并成只剩一个后 exGCD 求值即可。

Lucas 定理

适用于模数 $P$ 为质数的情况， $C _ m ^ n \bmod P = C _ {m \bmod P} ^ {n \bmod P} \times C _ {\lfloor \frac{m}{P} \rfloor} ^ {\lfloor \frac{n}{P} \rfloor}$ 。

exLucas 定理

适用于模数不是质数的情况，设 $P = \prod p _ i ^ {c _ i}$ ，我们可以求出 $C _ m ^ n$ 对 $p _ i ^ {c _ i}$ 取模的值，然后用 CRT 合并。这个直接用阶乘定义算，可能阶乘与 $p ^ c$ 不互质，推一下式子变成 $\frac{\frac{m!}{p _ x}}{\frac{n!}{p _ y} \times \frac{(m - n)!}{p _ z}} \times p ^ {x - y - z}$ 。

然后考虑怎么算上面那几个，我们设 $f _ p(i)$ 为 $i!$ 中的 $p$ 的因数个数，有 $f _ p(i) = \lfloor \frac{i}{p} \rfloor + f _ p (\lfloor \frac{i}{p} \rfloor)$ 。设 $fac _ i = \frac{i!}{p ^ {f _ p(i)}}$ ，这个就等价于上面推的那个，然后除完之后 $i! = 1 \times 2 \times \ldots \times (p - 1) \times (p + 1) \times \ldots \times (2p - 1) \times (2p + 1) \times \ldots$ 。

所以，有 $fac _ i = w _ i \times fac _ {\lfloor \frac{i}{p} \rfloor}$ ，其中 $w _ n = \prod _ {i = 1} ^ n i ^ {[p \nmid i]}$ 。这个可以用 $w _ i = (w _ {p ^ c - 1} ^ {\lfloor \frac{i}{p ^ c} \rfloor}) \times w _ {n \bmod p ^ c}$ 预处理。

所以最后 $C _ m ^ n \bmod p ^ c = p ^ {f _ p(m) - f _ p(n) - f _ p(m - n)} \times fac _ m \times fac _ n ^ {-1} \times fac _ {m - n} ^ {-1}$ ，求出每一个之后用 CRT 合并即可。

Wilson 定理

省流：对于质数 $P$ 有 $(P - 1)! \equiv -1 \pmod P$ 。

exWilson

TBU

Thanks for reading!

数学一家子

2025 10月 28 周二

2292 字 · 10 分钟

大数学照亮世界算法学习笔记数学 OI