加减乘除的取模运算
某些题目，由于要计算的答案非常大（超出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 | // 如果取模到 [0, MOD-1] 中，无论正负 |
