加法和乘法的取模
加法和乘法取模具有幂等性，直接计算即可。
需要注意的是，如果一行代码涉及三个（以上） 的乘法，需要注意是否会爆数据范围，保险的写法是 a * b % MOD * c % MOD。
同余
若 x 和 y 对于 m 同余，那么记作x ≡ y (mod m)
性质：
- 同余式中的加减法可以进行移项操作
减法的取模
根据同余的性质，可得一般地减法取模方法：
(x mod m + m) mod m
(a - b) mod m = （(a mod m - b mod m) + m) mod m。
这个公式不仅适用于 a - b <= 0也使用于大于零的情况。
除法的取模
- 结论：a 是 b 的倍数，并且 b 和 p 互质（b 不是 p 的倍数）
a / b ≡ (a * b ^ (p-2)) (mod p) - 引理 1：当 p 是质数且 1 <= i < p，有
C(p, i) ≡ 0 (mod p) - 引理 2：x、y 是任意整数，p 是任意质数，有
(x + y) ^ p ≡ x ^ p + y ^ p (mod p) - 费马小定理：
b ^ p ≡ b (mod p)
组合数的取模
计算组合数时，需要预先计算出阶乘和逆元，接着套公式即可。
C(n, m) = n! * 1 / (n - m)! * 1 / m!
const MOD = 1_000_000_007
const mx = 1_000_01 // 最大值
var fac[mx] int // 阶乘
var invF[mx] int // 阶乘的逆元 invF[i] = invF[i+1] * (i + 1)
func init() {
fac[0] = 1
for i := 1; i < mx; i++ {
fac[i] = i * fac[i-1] % MOD
}
invF[mx-1] = power(fac[mx-1], MOD-2)
for i := mx-1; i > 0; i-- {
invF[i-1] = invF[i] * i % MOD
}
}
func power(b, q int) int {
res := 1
for ;q > 0; q /= 2 {
if q & 1 == 1 {
res = res * b % MOD
}
b = b * b % 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
}总结
const MOD = 1_000_000_007
// 加
res := (a + b) % MOD
// 减法
// 结果落在 [1, MOD - 1)
res := (a + b + MOD) % MOD
// 乘（注意使用 64 位整数）
res := a * b % MOD
// 除
// power 是快速幂
res := a * power(b, MOD - 2, MOD) % MOD