《算法竞赛进阶指南》笔记

0x30 数学知识
- 0x33 同余
  - 概念与定理
    - 例题The Luckiest Number
  - 扩展欧几里得算法$(exgcd)$
    - 定理及概念
  - 乘法逆元
    - 概念
    - 例题 Sumdiv
  - 线性同余方程
    - 概念
    - 例题
  - 中国剩余定理
    - 定理
  - 高次同余方程
- 0x34 矩阵乘法
- 0x35 高斯消元与线性空间
  - 高斯消元
  - 线性空间
- 0x36 组合计数
  - 基本概念
  - 组合数的求法
  - 二项式定理
  - 多重集的排列数与组合数
  - Lucas 定理
  - Catalan 数列

0x30 数学知识

0x33 同余

概念与定理

定义: 如果$a\%m = b\%m$，则 $a$ 与 $b$ 模 $m$ 同余, $m$ 为正整数，记作 $a\equiv b\pmod m$

同余类: 对于 $\forall a \subset [0, m-1]$ ,集合 ${a+km}(k\subset Z)$ 的所有模 $m$ 同余，余数都是 $a$。该集合就是一个模 $m$ 的同余类，记为 $\bar{a}$。

完全剩余系: 模 $m$ 的同余类一共有 $m$ 个，分别为 $\bar{1},\bar{2},\dots,\overline{m-1}$ ,是一个完全剩余系。

简化剩余系: $1～m$ 中与 $m$ 互质的数代表的同余类共有$\varphi(m)$ 个，它们构成 $m$ 的简化剩余系，例如，模 $10$ 的简化剩余系为 ${\bar{1}, \bar{3}, \bar{7}, \bar{9}}$ 。( $\varphi(n)$ 大小为小于 $n$ 的所有与 $n$ 互质的正整数个数)

若 $a, b(1 ≤ a,b ≤ m)$ 与 $m$ 互质，则 $a*b$ 与 $m$ 也互质，也能属于 $m$ 的简化剩余系。

费马小定理: 若 $p$ 是质数，则对于任意整数 $a$,有 $a^p\equiv a\pmod p$。

欧拉定理: 若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\pmod n$，其中 $\varphi(n)$ 为欧拉函数。

（证明略）

其中，若 $p$ 是一个质数，则 $\varphi(p) = p - 1$。

欧拉定理的推论: 若正整数 $a,n$ 互质，则对于任意正整数 $b$,有 $a^b\equiv a^{b\mod \varphi(n)}\pmod n$。

对答案取模 $p$ 的应用技巧:

面对 $a+b,a-b,a*b$ 这种算式，先对 $a,b$ 分别对 $p$ 取模。
面对乘法算式, 根据欧拉定理的推论，先将底数对 $p$ 取模$、质数对 $\varphi(p)$ 取模，再计算乘方。
特别地，当 $a,n$ 不一定互质且 $b>\varphi(n)$ 时，有 $a^b\equiv a^{b\mod \varphi(n) + \varphi(n)}\pmod n$，即意味着，即便底数 $a$ 与模数 $n$ 不互质，也能把指数的规模给缩小。 （指数循环节证明）

例题The Luckiest Number

此题由欧拉函数引出一个推理:

满足 $a^x\equiv1\pmod n$ 的最小的 $x$, $x_0$ 是 $\varphi(n)$ 的约数。

此题启发点：

$x$ 个 $8$ 连起来的数可以写作 $8(10^x-1)/9$，题意是求最小的 $x$，满足 $L\mid 8(10^x -1)$。设 $d=gcd(L,8)$，然后推导运用引理。

扩展欧几里得算法$(exgcd)$

定理及概念

$Bezout$ 定理:对于任意整数 $a,b$ ,存在一对整数 $x,y$, 满足 $ax+by=gcd(a,b)$。

乘法逆元

概念

若整数 $b, m$ 互质，并且 $b\mid a$, 则存在一个整数 $x$, 使得 $a/b\equiv a*x\pmod m$。称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记作 $b^{-1}(mod\;m)$。
$\because a/b\equiv a*b^{-1}\equiv a/b*b*b^{-1}\pmod m$, $\therefore b*b^{-1}\equiv 1\pmod m$
如果 $m$ 是质数（之后用 $p$ 代表 $m$ )，并且 $b\lt p$ ,根据费马小定理，$b^{p-1}\equiv 1\pmod p$, 即 $b*b^{p-2}\equiv 1\pmod p$。因此，当模数 $p$ 为质数时，$b^{p-2}$ 即为 $b$ 的乘法逆元。
如果保证 $b,m$ 互质，那么乘法逆元可以通过求解同余方程 $b*x\equiv 1\pmod m$ 得到。
有了乘法逆元，在计数类问题遇到 $a/b$ 这样的除法算式，也可以先把 $a,b$ 各自对模数 $p$ 取模，再计算 $a*b^{-1}\mod p$ 作为最终的结果。当然，前提是必须保证 $b,p$ 互质（当 $p$ 是质数时，等价于 $b$ 不是 $p$ 的倍数）

例题 Sumdiv

这道题lyd老师的解法和yxc老师的解法各有不同，lyd老师的解法用到了乘法逆元，
依据等比数列求和分母是否为模数9901的倍数划分两种情况，yxc老师的解法则更偏向于推导。

解题思路

求 $A^B$ 的所有约数之和，对 $A$ 分解质因数为 $p_1^{c_1}*p_2^{c_2}*\cdots*p_n^{c_n}$，则 $A^B$ 的分解质因数为 $p_1^{c_1*B}*p_2^{c_2*B}*\cdots*p_n^{c_n*B}$。
故 $A^B$ 的约数之和为 $(1 + p_1 + p_1^2 +\cdots +p_1^{B*c_1})*(1+p_2+p_2^2+\cdots +p_2^{B*c_2})*\cdots*(1+p_n+p_n^2+\cdots+p_n^{B*c_n})$
对于上述式子单个括号而言，和为 $(p_i^{B*c_i + 1} - 1) / (p_i - 1)$ (等比数列求和)，
求这个和模 $mod$ 转换为 $a*b^{-1}\mod 9901$ 形式。
1. 当 $p_i - 1$ 不为 $9901$ 的倍数, 可以直接转换为其乘法逆元 $inv$, 用 $inv$ 代替除以 $(p_i - 1)$。
2. 当 $p_i - 1$ 为 $9901$ 的倍数，乘法逆元不存在，但是 $p_i\mod 9901 = 1$，所以 $1+p_i+p_i^2+\cdots+p_i^{B*c_i}\equiv B*c_i+1\pmod 1$

总结

还是乘法逆元最后一点说到的，有了乘法逆元，在计数类问题遇到 $a/b$ 这样的除法算式，可以对 $a,b$ 各自取模，再计算 $a*b^{-1}\mod p$，
尝试用乘法逆元 $b^{-1}\mod 1$ 替代除以 $b$。（尤其是 $b$ 是一个质数时）

线性同余方程

概念

定义: 给定整数 $a,b,m$，求一个整数 $x$ 满足 $a*x\mod b\pmod m$，或者给出无解。因为未知数的指数为 $1$，所以我们称之为一次同余方程，线性同余方程。

转换: $a*x\equiv b\pmod m$ 等价于 $a*x-b$ 是 $m$ 的倍数，设为 $-y$ 倍，则有 $a*x+m*y=b$。

有解情况: 当且仅当 $gcd(a,m)\mid b$ 存在。

求解: 先用欧几里得算法求出一组 $x_0, y_0$，满足 $a*x_0 + m*y_0=gcd(a,m)$，然后 $x=x_0*b/gcd(a,m)$ 就是原线性同余方程的一个解。

通解: 所有模 $m/gcd(a.m)$ 与 $x$ 同余的整数。

例题

题意: 求关于 $x$ 的同余方程 $a*x\equiv 1\pmod b$ 的最小正整数解。输入数据保证一定有解

解题思路

方程有解当且仅当 $gcd(a,m)\mid 1 \;即\;gcd(a, b) = 1$，方程改写为 $a*x + b*y=1$
求出方程与一组特解 $x_0,y_0$ ，通解为所有模 $b$ 与 $x_0$ 同余的整数。通过取模操作将解范围移动到 $1～b$ 之间，得到我们想要的解

中国剩余定理

定理

设 $m_1,m_2,\cdots,m_n$ 是两两互质的整数， $m=\prod_{i=1}^nm_i, M_i=m/m_i$, $t_i$ 是线性同余方程
$M_it_i\equiv 1\pmod m_i$ 的一个解($M_i$ 的乘法逆元)。对于任意 $n$ 个整数 $a_1,a_2,\cdots,a_n$, 方程组

\[\left\{ \begin{array}{c} x\equiv a_1\pmod m_1 \\ x\equiv a_2\pmod m_2 \\ \vdots \\ x\equiv a_n\pmod m_n \end{array} \right. \]

有整数解，解为 $x=\Sigma_{i=1}^na_iM_it_i$。

作用: 使得我们很容易解出模数两两互质的线性同余方程组的一个特解，通解为 $x+km(k\subset Z)$，求最小的非负整数解，$x$ 对 $m$ 取模即可。

高次同余方程

0x34 矩阵乘法

0x35 高斯消元与线性空间

高斯消元

线性空间

0x36 组合计数

基本概念

加法原理: 完成一件事有 $n$ 类方法，其中第 $i$ 类方法包括 $a_i$ 种不同的方法，且方法之间相互独立，则完成这件事共有 $a_1+a_2+\ldots+a_n$ 种不同方法。

乘法原理: 完成一件事要 $n$ 个步骤，其中第 $i$ 个步骤有 $a_i$ 种不同的方法，方法、步骤之间相互独立,则完成这件事共有 $a_1*a_2*\cdots*a_n$ 种不同方法。

排列数: 从 $n$ 个不同元素中依次取出 $m$ 个元素排成一列，产生的不同排列的数量为：

\[A_n^m(也可记作P_n^m)=\frac{n!}{(n-m)!}=n*(n-1)*\cdots*(n-m+1) \]

组合数: 从 $n$ 个不同的元素中取出 $m$ 个组成一个集合（无顺序），产生的不同集合数量为：

\[C_n^m=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*\cdots*(n-m+1)}{m*(m-1)*\cdots*2*1} \]