2021年9月24日待完成

某些题目，由于要计算的答案非常大（超出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 $有： $$ \begin{align} (a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m \end{align} $$

第二个恒等式： $$ \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} $$

同样有： $$ \begin{align} (a\cdot b) \bmod m &=((a \bmod m)\cdot (a \bmod m)) \bmod m \end{align} $$

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

注意：如果涉及到幂运算，不能随意取模。如果指数为整数，可以用快速幂。

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

smilelc3 / leetcode

2021年9月24日待完成 #12