模与相关运算

模运算

当结果数值太大的时候，题目经常会让你返回取模的结果，这时最常用的模为： $10^9 + 7$ 和 $10^9 + 9$ ，这两个数都是质数，而且比32位数的最大值一半略小。

此时按模运算时，中间结果往往也都存储模之后的结果，这时有以下等式可以利用：

(a+b) \mod m = (a \mod m + b \mod m) \mod m \\ (a-b) \mod m = (a \mod m - b \mod m) \mod M \\ (a \cdot b) \mod m = (a \mod m) \cdot (b \mod m) \mod m \\ a^b \mod m = (a \mod m) ^ b \mod m

写代码时，需要注意防止出现负数，以及整数越界的情况，以下是一些通用的写法：

int a,b,c,y;                // 以下假设所有数的真实数值都为正
const int M = 1e9 + 7;
...
y = (a + b) % M;            // a,b都小于INT32_MAX一半，所以直接加没关系
y = ((ll)a + b + c) % M;    // 三个数加的时候，就要小心越界，转成long long是简单的办法
y = (a - b + M) % M;        // 减法会出现负数，加一个M就可以了
y = (ll)a * b % M;          // 乘法也要小心越界
y = (ll)a * b % M * c % M;  // 连乘要及时取模，防止越long long的界

快速幂

下面是用递归快速求幂的方法：

int modpow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int y = modpow(x, p/2);         // 不能modpow() * modpow()，会导致重复计算
    y = (ll)y * y % M;
    return p % 2 ? (ll)y * x % M : y;
}

另一办法是基于二进制位求(binpow)。

MOD除法 / 求逆

有时在模运算下需要做除法，这时没法直接做，但是很多时候可以用费马小定理（Fermat's little theorem）取得类似效果。当 $p$ 是质数的时候，根据费马小定理有：

a^p = a \mod p \\ a^{p-2} \cdot a = 1 \mod p

容易看到两个式子是等价的，所以当 $p$ 是质数的时候， $a^{p-2}$ 是 $a$ 的逆元素。所以使用上面的快速幂，就可以将逆元素计算出来，得到除法一样的结果。

另外，对于 $p=10^9+7$ ，有简单的结果： $2^{-1}=5 \cdot 10^8 + 4$ 。