ThinkLab

在算法与程序设计中，当计算结果过大（超出 64 位整数的范围）时，通常需要将答案对某个特定数值（如 $10^9 + 7$）取模。若处理不当，极易导致计算结果错误（WA）或因大整数运算导致超时（TLE）。本笔记将全面解析模运算的数学原理及编程实现技巧。

1. 加法和乘法的取模

在计算多个数字的乘积或连加时，若不在计算的中间步骤及时取模，极易发生溢出。只需关注影响最终结果的对应余数部分即可。

1.1 模运算恒等式

处理加法与乘法取模时，常依赖以下两个恒等式（其中 $\bmod$ 表示取模运算，对应编程语言中的 %）：

加法恒等式： $$(a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$

乘法恒等式： $$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$$

1.2 恒等式证明

基于带余除法，任意整数 $a$ 均可表示为 $a = qm + r$（$m \neq 0$）。其中 $q$ 为商，$r$ 为余数（即 $r = a \bmod m$）。设定： $a = q_1m + r_1$ $b = q_2m + r_2$

加法证明过程： $$(a+b) \bmod m$$ $$= ((q_1+q_2)m + r_1 + r_2) \bmod m$$ $$= (r_1 + r_2) \bmod m$$ $$= ((a \bmod m) + (b \bmod m)) \bmod m$$

乘法证明过程： $$(a \cdot b) \bmod m$$ $$= (q_1q_2m^2 + (q_1r_2 + q_2r_1)m + r_1r_2) \bmod m$$ $$= (r_1r_2) \bmod m$$ $$= ((a \bmod m) \cdot (b \bmod m)) \bmod m$$

借助上述恒等式，可以在循环计算的每一步对加法和乘法结果取模。

注意： 若涉及幂运算，指数部分不能随意取模。若指数在 64 位整数范围内，可使用快速幂算法；若超出该范围，则需借助欧拉降幂等进阶定理。

2. 同余理论基础

在探讨减法和除法的取模规则前，需要引入“同余”的概念。

2.1 同余的定义

对于两个整数 $a$ 和 $b$，若 $(a-b) \bmod m = 0$（即 $a-b$ 是 $m$ 的倍数），则称 $a$ 与 $b$ 关于模 $m$ 同余，记作： $$a \equiv b \pmod m$$

特例：$m \equiv 0 \pmod m$

2.2 同余式的基本性质

乘法性质： 在同余式两边乘以同一个整数，同余式依然成立。
- 证明：若 $a \equiv b \pmod m$，则 $a-b$ 是 $m$ 的倍数。对于任意整数 $k$，$k(a-b) = ka - kb$ 也是 $m$ 的倍数，故 $ka \equiv kb \pmod m$。
移项与加减性质： 同余式中的加减法可以移项；在两边加上或减去同一个整数，同余式仍然成立。
- 例如：$a+b \equiv c+d \pmod m$ 可移项为 $a-c \equiv d-b \pmod m$。
- 特例（无符号 32 位整数溢出）：$-1 \equiv 4294967295 \pmod{2^{32}}$。

3. 负数和减法的取模

当计算过程中产生减法时，结果可能为负数。由于不同编程语言对负数取模的底层实现存在差异，未处理的负数取模极易导致错误。

3.1 负数调整策略

根据同余定义，如 $-17 \equiv 3 \pmod{10}$。将负数调整为非负数，可通过“模 $m$ 加 $m$”的方式进行。一般地，若 $x < 0$ 且 $0 \le y < m$，则 $x \equiv y \pmod m$ 等同于： $$x \bmod m + m = y$$

为了免去判断 $x$ 是否小于零的步骤，更普适的代码处理范式为： $$(x \bmod m + m) \bmod m$$ 此公式确保了无论 $x$ 是正、负还是零，最终结果必然落入区间 $[0, m-1]$。

3.2 减法恒等式

在掌握负数调整策略后，减法取模可表示为： $$(a-b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$$

4. 除法的取模与费马小定理

除法无法像加减乘一样直接将取模运算分配到分子和分母上。当模数为质数时，通常需将其转化为乘法运算。

4.1 核心结论

如果 $p$ 是一个质数，$a$ 是 $b$ 的倍数，且 $b$ 和 $p$ 互质（即 $b$ 不是 $p$ 的倍数），则存在如下结论： $$\frac{a}{b} \bmod p = (a \cdot b^{p-2}) \bmod p$$ 其中，除以 $b$ 在模 $p$ 意义下等效于乘以 $b$ 的逆元（$b^{-1} \bmod p$）。

4.2 费马小定理的推导与证明

证明上述除法转换的基石是费马小定理。需要先引入两个引理。

引理 1： 当 $p$ 是质数且 $1 \le i \le p-1$ 时，组合数 $\binom{p}{i} \equiv 0 \pmod p$。

证明：组合数展开式为 $\frac{p!}{i!(p-i)!}$。因 $1 \le i \le p-1$，分母不包含质因数 $p$。而分子存在质数 $p$，且组合数必为整数，故结果能被 $p$ 整除。

引理 2（基于二项式定理）： 对于任意整数 $x, y$ 和质数 $p$，有 $(x+y)^p \equiv x^p + y^p \pmod p$。

证明：二项式定理展开后，除第一项 $x^p$ 和最后一项 $y^p$ 外，其余项均含有系数 $\binom{p}{i}$。由引理 1 可知，中间项均为 $p$ 的倍数，均可消去。

定理（费马小定理）： 对于任意整数 $b$ 和质数 $p$，有： $$b^p \equiv b \pmod p$$

归纳证明：
1. 当 $b=0$ 时，$0^p \equiv 0 \pmod p$ 成立。
2. 假设当 $b=k$ 时成立，即 $k^p \equiv k \pmod p$。
3. 当 $b=k+1$ 时，依据引理 2，$(k+1)^p \equiv k^p + 1^p \pmod p$。代入归纳假设后，得 $(k+1)^p \equiv k+1 \pmod p$。定理成立。

将 $b^p \equiv b \pmod p$ 变形为 $b(b^{p-1}-1) \equiv 0 \pmod p$。若 $b$ 不是 $p$ 的倍数，则 $b^{p-1}-1$ 必为 $p$ 的倍数。移项后得出模逆元的核心形式： $$b^{p-1} \equiv 1 \pmod p$$ 同乘 $\frac{a}{b}$ 即可得出 $\frac{a}{b} \bmod p \equiv a \cdot b^{p-2} \pmod p$。计算 $b^{p-2} \bmod p$ 时，通常配合快速幂算法实现。

5. 常见模运算代码范式汇总

在算法题目中，设模数常量 MOD = 1_000_000_007，标准的四则运算取模写法如下：

MOD = 1000000007

# 加法
(a + b) % MOD

# 减法 (确保结果非负)
(a - b + MOD) % MOD

# 通用取模 (无论正负均映射到 [0, MOD-1])
(a % MOD + MOD) % MOD

# 乘法 (注意多重相乘时需步步取模以防溢出)
a * b % MOD * c % MOD

# 除法 (使用快速幂 qpow 求逆元)
a * qpow(b, MOD - 2, MOD) % MOD
# Python 可直接简写为:
a * pow(b, -1, MOD) % MOD

6. 附录：组合数的取模计算

计算组合数 $C(n, m)$ 的公式为： $$C(n, m) = \frac{n!}{m!(n-m)!}$$

在取模场景下，可利用除法取模定理将分母转化为求逆元。实际编码中，需要提前预处理阶乘（fac）及其逆元（inv_f）。

阶乘递推式： $n! = (n-1)! \cdot n$
阶乘逆元倒推式： $\frac{1}{(n-1)!} = \frac{1}{n!} \cdot n$ （即先用快速幂求出最大项的逆元，再逆向推演以降低时间复杂度）

模板示例：

MOD = 1_000_000_007
MX = 100_001

# 预处理阶乘
fac = [0] * MX
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

# 预处理阶乘逆元
inv_f = [0] * MX
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % MOD

def comb(n: int, m: int) -> int:
    """计算从 n 个元素中选择 m 个元素的组合数"""
    if 0 <= m <= n:
        return fac[n] * inv_f[m] % MOD * inv_f[n - m] % MOD
    return 0

深入理解模运算