本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。 原文链接：https://leetcode.cn/circle/discuss/mDfnkW/

---

前言

某些题目，由于要计算的答案非常大（超出 64 位整数的范围），会要求把答案对 ${10}^9+7$ 取模。如果没有处理得当的话，会 WA（错误）或者 TLE（超时）。

例如计算一堆数字的乘积，如果没有及时取模，乘法会溢出（例如计算结果超出 C++ 中 long long 的最大值），从而得到和预期不符的答案。对于 Python 来说，虽然没有溢出的问题，但大整数（big integer）之间的运算并不是 $\mathcal{O}(1)$ 的，可能会导致 TLE。

如何正确地取模呢？

加法和乘法的取模

如果让你计算 $1234\times 6789$ 的个位数，你会如何计算？

由于只有个位数会影响到乘积的个位数，那么 $4\times 9=36$ 的个位数 $6$ 就是答案。

对于 $1234+6789$ 的个位数，同理，$4+9=13$ 的个位数 $3$ 就是答案。

你能把这个结论抽象成数学等式吗？

一般涉及到取模的题目，会用到如下两个恒等式，其中 $mod$ 表示取模运算（modulo），即编程语言中的 %。上面计算的是 $m=10$ 的情况。

$$(a+b)modm=((amodm)+(bmodm))modm$$$$(a\cdot b)modm=((amodm)\cdot (bmodm))modm$$

证明：根据带余除法，任意整数 $a$ 都可以表示为 $a=qm+r(m\ne 0)$，其中整数 $q$ 为 $a$ 除以 $m$ 的商（quotient），整数 $r$ 为 $a$ 除以 $m$ 的余数（remainder），即 $r=amodm$。

设整数 $a=q_{1}m+r_1,b=q_{2}m+r_2$。

第一个恒等式：

$$\begin{array}{rl}& (a+b)modm\\ =& ((q_1+q_2)m+r_1+r_2)modm\\ =& (r_1+r_2)modm\\ =& ((amodm)+(bmodm))modm\end{array}$$

第二个恒等式：

$$\begin{array}{rl}& (a\cdot b)modm\\ =& (q_1{q}_2{m}^2+(q_1{r}_2+q_2{r}_1)m+r_1{r}_2)modm\\ =& (r_1{r}_2)modm\\ =& ((amodm)\cdot (bmodm))modm\end{array}$$

根据这两个恒等式，我们可以在计算过程中（例如循环），对加法和乘法的结果取模，而不是在循环结束后再取模。

注：如果涉及到幂运算，指数是不能随意取模的。如果指数在 64 位整数的范围内，可以用快速幂计算，原理见【图解】一张图秒懂快速幂；如果指数超出 64 位整数的范围，见 欧拉降幂。

如果计算过程中有减法，可能会产生负数，处理不当也会导致 WA。如何正确处理这种情况呢？

同余

首先引入同余（congruence modulo）的概念。

两个整数 $a$ 和 $b$，如果 $(a-b)modm=0$（也就是 $a-b$ 是 $m$ 的倍数），则称 $a$ 与 $b$ 关于模 $m$ 同余，记作

$$a\equiv b(\mathrm{mod}m)$$

上式也称作模 $m$ 的同余式，简称同余式。

例如 $42\equiv 12(\mathrm{mod}10)$，$-17\equiv 3(\mathrm{mod}10)$。

特别地，有

$$m\equiv 0(\mathrm{mod}m)$$

定理：在同余式两边乘以同一个整数，同余式仍然成立。

证明：设 $a\equiv b(\mathrm{mod}m)$，设 $k$ 是一个整数。根据同余的定义，$a-b$ 是 $m$ 的倍数，所以 $k(a-b)=ka-kb$ 也是 $m$ 的倍数，所以 $ka\equiv kb(\mathrm{mod}m)$。

同余式的移项

同余式中的加减法可以移项。

例如

$$a+b\equiv c+d(\mathrm{mod}m)$$

可以移项得到

$$a-c\equiv d-b(\mathrm{mod}m)$$

证明：$a+b\equiv c+d(\mathrm{mod}m)$ 意味着 $(a+b)-(c+d)$ 是 $m$ 的倍数，即 $(a-c)-(d-b)$ 是 $m$ 的倍数，所以 $a-c\equiv d-b(\mathrm{mod}m)$。

推论：在同余式两边加上（减去）同一个整数，同余式仍然成立。

证明：设 $a\equiv b(\mathrm{mod}m)$，左边加上 $0=x-x$，得到 $a+(x-x)\equiv b(\mathrm{mod}m)$，移项得 $a+x\equiv b+x(\mathrm{mod}m)$。

特别地，在同余式

$$0\equiv m(\mathrm{mod}m)$$

的两边加上 $-x$，得

$$-x\equiv m-x(\mathrm{mod}m)$$

例如在无符号 $32$ 位整数中，$-1$ 溢出得到 $2^{32}-1=4294967295$，用数学语言描述，就是

$$-1\equiv 4294967295(\mathrm{mod}{2}^{32})$$

负数和减法的取模

根据同余的定义，我们有 $-17\equiv 3(\mathrm{mod}10)$。

怎么从 $-17$ 得到 $3$？

我们可以 $-17+10+10=3$。也可以 $-17mod10+10=-7+10=3$，这样只需加一次 $m$。

一般地，如果 $x<0$ 且 $0\le y<m$，则 $x\equiv y(\mathrm{mod}m)$ 相当于

$$xmodm+m=y$$

也就是用「模 $m$ 加 $m$」，把 $x$「调整」为非负数。

为避免判断 $x<0$，更一般的写法是

$$(xmodm+m)modm$$

这样无论 $x$ 是正是负还是零，运算结果都会落在区间 $[0,m-1]$ 中。

对于减法来说，当 $a-b\ge 0$ 时，前文中的加法恒等式可以调整为

$$(a-b)modm=((amodm)-(bmodm)+m)modm$$

注 1：代码实现时，在计算中产生负数也可以，在最后用 $(xmodm+m)modm$ 调整就行。

注 2：Python 用户可以忽略，只要 $m$ 是正整数，取模运算的结果就一定是非负整数。

以上是关于加法、减法和乘法的模运算规则，那么除法呢？

除法的取模

如果要计算 ${\displaystyle \frac{24}{8}}mod5$，可以像加法或乘法那样，写成 ${\displaystyle \frac{24mod5}{8mod5}}mod5$ 吗？这不行，${\displaystyle \frac{24mod5}{8mod5}}={\displaystyle \frac{4}{3}}$ 甚至不是一个整数。

先说结论，如果 $p$ 是一个质数，$a$ 是 $b$ 的倍数且 $b$ 和 $p$ 互质（$b$ 不是 $p$ 的倍数），那么有

$${\displaystyle \frac{a}{b}}modp=(a\cdot b^{p-2})modp$$

上式中 $a$ 和 $b$ 可以是很大的数，例如 $a=100!,b=50!50!$。

由于 ${10}^9+7$ 是一个质数，所以上式可用于要求对 ${10}^9+7$ 取模的题目。如果推导出了包含除法的式子，可以用上式转换成乘法，并用快速幂计算 $b^{p-2}modp$。

下面是证明。

引理 1：当 $p$ 是质数且 $1\le i\le p-1$ 时，有

$$(\genfrac{}{}{0ex}{}{p}{i})\equiv 0(\mathrm{mod}p)$$

其中

$$(\genfrac{}{}{0ex}{}{p}{i})={\displaystyle \frac{p!}{i!(p-i)!}}$$

证明：注意当 $1\le i\le p-1$ 时，${\displaystyle \frac{p!}{i!(p-i)!}}$ 的分母是不包含 $p$ 的。由于分子包含 $p$ 且 ${\displaystyle \frac{p!}{i!(p-i)!}}$ 是整数，所以 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{i})}$ 可以被 $p$ 整除，即 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{i})}\equiv 0(\mathrm{mod}p)$。

注：如果 $p$ 不是质数，分母可能被 $p$ 整除，上面的结论不一定成立。例如 $p=4,i=2$ 的情况，${\displaystyle (\genfrac{}{}{0ex}{}{p}{i})}=6$，不是 $p=4$ 的倍数。

引理 2：对于任意整数 $x$ 和 $y$ 和任意质数 $p$，有

$$(x+y{)}^p\equiv x^p+y^p(\mathrm{mod}p)$$

证明：根据二项式定理，有

$$(x+y{)}^p=(\genfrac{}{}{0ex}{}{p}{0})x^p{y}^0+(\genfrac{}{}{0ex}{}{p}{1})x^{p-1}{y}^1+(\genfrac{}{}{0ex}{}{p}{2})x^{p-2}{y}^2+\cdots +(\genfrac{}{}{0ex}{}{p}{p-1})x^1{y}^{p-1}+(\genfrac{}{}{0ex}{}{p}{p})x^0{y}^p$$

根据引理 1，除了第一项和最后一项以外，其余项都是 $p$ 的倍数，于是

$$(x+y{)}^p\equiv x^p+y^p(\mathrm{mod}p)$$

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

$$b^p\equiv b(\mathrm{mod}p)$$

证明：当 $b=0$ 时，$0^p\equiv 0(\mathrm{mod}p)$ 成立。

假设 $b=k$ 时原命题成立，即

$$k^p\equiv k(\mathrm{mod}p)$$

根据引理 2，我们有

$$(k+1{)}^p\equiv k^p+1^p(\mathrm{mod}p)$$

根据归纳假设，得

$$(k+1{)}^p\equiv k+1(\mathrm{mod}p)$$

即当 $b=k+1$ 时，原命题成立。

根据数学归纳法，原命题对于 $b\ge 0$ 成立。对于 $b<0$ 的情况同理。

$b^p\equiv b(\mathrm{mod}p)$ 变形得 $b(b^{p-1}-1)\equiv 0(\mathrm{mod}p)$，如果 $b$ 不是 $p$ 的倍数，那么 $b^{p-1}-1$ 必须是 $p$ 的倍数（注意 $p$ 是质数），即 $b^{p-1}-1\equiv 0(\mathrm{mod}p)$，移项得

$$b^{p-1}\equiv 1(\mathrm{mod}p)$$

两边同时乘以 ${\displaystyle \frac{a}{b}}$（$a$ 是 $b$ 的倍数），得

$$a\cdot b^{p-2}\equiv {\displaystyle \frac{a}{b}}(\mathrm{mod}p)$$

即

$${\displaystyle \frac{a}{b}}modp=(a\cdot b^{p-2})modp$$

注：除以 $b$ 相当于乘以 $b$ 的逆元 $b^{-1}modp$。在概率期望等题目中，会遇到 $a$ 不是 $b$ 的倍数的情况，这些题目通常会规定计算 $(a\cdot b^{-1})modp$，计算方法和上式一样。

总结

代码实现时，上面的加减乘除通常是这样写的：

MOD = 1_000_000_007

// 加
(a + b) % MOD

// 减，b 在 [0,MOD-1] 中，通过 +MOD 保证结果非负
(a - b + MOD) % MOD

// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD

// 乘（注意使用 64 位整数）
a * b % MOD

// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD

// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD

其中 $\mathtt{\text{qpow}}$ 为快速幂，具体请看【图解】一张图秒懂快速幂。

注：Python 内置快速幂函数 pow(x, y, m) 用于计算 $x^{y}modm$。特别地，除法也可以写成 a * pow(b, -1, MOD) % MOD。

总之，如果发现解答错误，可以检查下代码，看看是不是哪里漏掉取模了。

附：组合数的计算

关于组合数，我们需要预处理阶乘及其逆元，然后利用公式

$$C(n,m)={\displaystyle \frac{n!}{m!(n-m)!}}=n!\cdot {\displaystyle \frac{1}{m!}}\cdot {\displaystyle \frac{1}{(n-m)!}}$$

计算。

对于阶乘 $n!$，可以用

$$n!=(n-1)!\cdot n$$

递推计算。

对于阶乘的倒数 ${\displaystyle \frac{1}{n!}}$，可以先计算 $\mathit{\text{N}}!$ 的逆元（其中 $N$ 是 $n$ 的最大值），然后用

$${\displaystyle \frac{1}{(n-1)!}}={\displaystyle \frac{1}{n!}}\cdot n$$

倒着递推计算。

模板代码如下：

MOD = 1_000_000_007
MX = 100_001  # 根据题目数据范围修改

fac = [0] * MX  # fac[i] = i!
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

inv_f = [0] * MX  # inv_f[i] = i!^-1
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

# 从 n 个数中选 m 个数的方案数
def comb(n: int, m: int) -> int:
    return fac[n] * inv_f[m] * inv_f[n - m] % MOD if 0 <= m <= n else 0

class Solution:
    def solve(self, nums: List[int]) -> int:
        # 预处理的逻辑写在 class 外面，这样只会初始化一次

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 100_001; // 根据题目数据范围修改

    private static final long[] F = new long[MX]; // F[i] = i!
    private static final long[] INV_F = new long[MX]; // INV_F[i] = i!^-1 = pow(i!, MOD-2)

    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        F[0] = 1;
        for (int i = 1; i < MX; i++) {
            F[i] = F[i - 1] * i % MOD;
        }

        INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            INV_F[i - 1] = INV_F[i] * i % MOD;
        }
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

    // 从 n 个数中选 m 个数的方案数
    private long comb(int n, int m) {
        return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
    }

    public int solve(int[] nums) {
        
    }
}

const int MOD = 1'000'000'007;
const int MX = 100'001; // 根据题目数据范围修改

long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1 = qpow(i!, MOD-2)

long long qpow(long long x, int n) {
    long long res = 1;
    for (; n; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) {
        F[i] = F[i - 1] * i % MOD;
    }

    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }
    return 0;
}();

// 从 n 个数中选 m 个数的方案数
long long comb(int n, int m) {
    return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}

class Solution {
public:
    int solve(vector<int>& nums) {
        // 预处理的逻辑写在 class 外面，这样只会初始化一次
    }
};

const mod = 1_000_000_007
const mx = 100_001 // 根据题目数据范围修改

var fac [mx]int  // fac[i] = i!
var invF [mx]int // invF[i] = i!^-1 = pow(i!, mod-2)

func init() {
    fac[0] = 1
    for i := 1; i < mx; i++ {
        fac[i] = fac[i-1] * i % mod
    }

    invF[mx-1] = pow(fac[mx-1], mod-2)
    for i := mx - 1; i > 0; i-- {
        invF[i-1] = invF[i] * i % mod
    }
}

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

// 从 n 个数中选 m 个数的方案数
func comb(n, m int) int {
    if m < 0 || m > n {
        return 0
    }
    return fac[n] * invF[m] % mod * invF[n-m] % mod
}

func solve(nums []int) int {
    // 预处理的逻辑写在 init 函数中，这样只会初始化一次
}

如果模数不是质数呢？见 3463. 判断操作后字符串中的数字是否相等 II。

取模练习

• 3379. 转换数组 做到 $\mathcal{O}(n)$
• 1018. 可被 5 整除的二进制前缀 1376

快速幂练习

• 2961. 双模幂运算 1451
• 2550. 猴子碰撞的方法数 1663
• 372. 超级次方

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府