某些题目，由于要计算的答案非常大（超出64位整数的范围），会要求把答案对
\(10^9 +
7\) 取模。如果在计算中途没有处理得当的话，会出现WA（错误）或则TLE（超时）。
例如计算多项乘积时，如果没有中途及时取模，乘法结果会溢出（例如C/C++），从而得到非预期的答案
。对于 Python 来说，虽然没有溢出，但是大整数（big
integer）之间的运算不是 \(O(1)\) ，可能会导致LTE。
加法和乘法的取模
一般涉及到取模（\(\bmod\) ）的题目，会用到如下两个恒等式 \[
\begin{align}
(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 \\
\end{align}
\]
证明 ：根据带余除法，\({\forall} a \in
\mathbb{z}\) ，都可以表示为\(a = qm + r\
(m \neq 0)\) ，其中整数\(q\) 为\(a\) 除以\(m\) 的商（quotient），整数\(r\) 为\(a\) 除以\(m\) 的余数（remainder），即\(r = a \bmod m\) 。
设\(a = q_1 m + r_1\) ，\(b = q_2 m + r_2\) 。 第一个恒等式： \[
\begin{align}
(a+b) \bmod m &= (q_1 m + r_1 +q_2 m + r_2) \bmod m \\
&=((q_1 + q_2)m + r_1 + r_2) \bmod m \\
&=(r_1 + r_2) \bmod m
\end{align}
\] 又因为\(r_1 = a \bmod
m\) ，\(r_2 = b \bmod m\) 有：
\[
(a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m
\]
第二个恒等式： \[
\begin{align}
(a\cdot b) \bmod m &= ((q_1 m + r_1)(q_2 m + r_2)) \bmod m \\
&= (q_1 q_2 m^2 + (q_1 r_2 + q_2 r_1)m + r_1 r_2) \bmod m \\
&=(r_1 r_2) \bmod m
\end{align}
\]
同样有： \[
(a\cdot b) \bmod m =((a \bmod m)\cdot (a \bmod m)) \bmod m
\]
根据这两个恒等式，我们可以在计算过程中（例如循环中），对加法和乘法的结果取模，而不是在计算最终结果后再取模。
注意：如果涉及到幂运算，不能随意取模。如果指数为整数，可以用快速幂 。
如果计算过程中有减法，可能会产生负数，处理不当也会导致
WA。如何正确处理这种情况呢？
同余
首先引入同余（congruence modulo） 的概念。 两个整数\(a\) ，\(b\) ，若它们除以正整数\(m\) 所得的余数相等，则称\(a\) ，\(b\) 对于模\(m\) 同余，记作： \[
a \equiv b \pmod m
\]
例如\(42 \equiv 12 \pmod
{10}\) ，因为\(42\) 和\(12\) 都可以被\(10\) 整除，余数都是\(2\) 。
负数的取模
对于负数，我们可以将其转化为对应的非负数再取模。例如，\(-17 \bmod 10\) 可以转化为\(((-17 \bmod 10) +10) \bmod 10 = (-7 +10) \bmod
10\) ，结果是\(3\) 。
也就是说，如果我们发现 \((x \bmod m) <
0\) ，可以加上一个\(m\) ，得到非负数。
为避免判断\(x\bmod m <
0\) ，可以写成 \[
(x \bmod m + m) \bmod m
\]
这样无论\(x\) 是否为负数，运算结果都会落在区间\([0,m−1]\) 中。
除法的取模
如果要计算\(\frac{24}{8} \bmod
5\) ，如果像加法或乘法处理，写成\(\frac{24 \bmod 5}{8 \bmod 5} \bmod 5 =
\frac{4}{3}\) ，明显不是正确答案\(3\) 。先有结论：
如果\(p\) 是一个质数，\(a\) 是\(b\) 的倍数且\(b\) 和\(p\) 互质，那么有 \[
\frac{a}{b} \bmod p = (a \cdot b^{p-2}) \bmod p
\]
如果实际题目中推导出了包含除法的求余式，可以用上式转换成乘法，并用快速幂计算\(b^{p-2} \bmod p\) 。
证明 ：
引理1： 当\(p\) 是质数且\(1
\leq i \leq p-1\) 时，有 \[
\mathrm{C}_p^i \equiv 0 \pmod p
\]
其中 \[
\mathrm{C}_p^i = \frac{p!}{i!(p-i)!}
\] 证明：当\(p\) 是质数且\(1 \leq i \leq p-1\) 时，\(\frac{p!}{i!(p-i)!}\) 分母一定不含\(p\) ，由于分子中包含\(p\) 且\(\mathrm{C}_p^i\) 为整数，所以\(\mathrm{C}_p^i\) 一定能被\(p\) 整除，即\(\mathrm{C}_p^i \equiv 0 \pmod p\) 。
引理2： 根据二项式定理 ，有
\[
(x+y)^p = \sum_{k=0}^{p}{\mathrm{C}_p^k x^{p-k} y^k} =
\sum_{k=0}^{p}{\mathrm{C}_p^k x^k y^{p-k}}
\]
当\(p\) 为质数，且\(x, y \in \mathbb{z}\) 时，除去\(k=0\) 和\(k=p\) 两项，根据引理1 ，其余项与\(0\) 关于\(p\) 同余。即 \[
\sum_{k=1}^{p-1}{\mathrm{C}_p^k x^{p-k} y^k} \equiv 0 \pmod p
\] 拆分 \[
\begin{align}
(x+y)^p &= \mathrm{C}_p^0 x^p y^0 + \sum_{k=1}^{p-1}{\mathrm{C}_p^k
x^{n-k} y^k} + \mathrm{C}_p^p x^0 y^p \\
&=x^p + y^p + \sum_{k=1}^{p-1}{\mathrm{C}_p^k x^{n-k} y^k}
\end{align}
\]
于是当\(p\) 为质数，且\(x, y \in \mathbb{z}\) 时，有： \[
(x+y)^p \equiv x^p + y^p \pmod p
\]
根据费马小定律 ，对任意整数\(a\) 和任意质数\(p\) ，有： \[
a^p \equiv a \pmod p
\] 证明：当\(a = 0\) 时，\(0^p \equiv 0 \pmod p\) 成立；
已知引理2 ，通过归纳法，我们可以得到： \[
(x_1+ ... +x_n)^p \equiv x_1^p + ... + x_n^p \pmod p
\]
如果将\(a\) 展开为\(a\) 个\(1\) 相加，\(a=1+...+1\) ,代入上式有： \[
a^p \equiv (1+ ... +1)^p \equiv 1^p + ... + 1^p \equiv a \pmod p
\]
根据数学归纳法，原命题对于 \(a\ge
0\) 成立。对于\(a <
0\) 的情况同理，证明完毕。
如果\(a\) 不是\(p\) 的倍数，费马小定理也可以写成更加常用的一种形式：
\[
a^{p-1} \equiv 1 \pmod p
\] 如果\(a\) 是\(p\) 的倍数，显然有：\(a^{p-1} \equiv 0 \pmod p\) 。
在\(a\) 不是\(p\) 的倍数的前提下，两边同时乘以\(\frac{b}{a}\) ，有 \[
b \cdot a^{p-2} \equiv \frac{b}{a} \pmod p
\]
即 \[
\frac{b}{a} \bmod p = (b \cdot a^{p-2}) \bmod p
\]
总结
1 2 3 4 5 6 7 8 9 // 如果取模到 [0, MOD-1] 中，无论正负 (a % MOD + MOD) % MOD // 多个数相乘，要步步取模，防止溢出 (a * b * c) % MOD = a * b % MOD * c % MOD // 除（MOD 是质数且 b 不是 MOD 的倍数） (a / b) % MOD = a * qpow(b, MOD-2, MOD) % MOD // qpow 是快速幂
