模运算

加法和乘法的取模

加法和乘法取模具有幂等性，直接计算即可。

需要注意的是，如果一行代码涉及三个（以上） 的乘法，需要注意是否会爆数据范围，保险的写法是 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
}

组合模 10

最近刷到一些题目考察组合数模 10，由于 10 并不是质数，因此不能使用费马小定理计算逆元。需要采用其他方式计算模 10 情况下的阶乘逆元。

核心思想：计算n的逆元，将n转换为n' * 2^q * 5^p，于是有n^-1 = n'^-1 * 2^-q * 5^-p。因为n'和 10 互质，即gcd(n', 10) = 1，所以可以通过欧拉定理计算n'^-1。

const MOD = 10
const mx = 1_000_01 // 最大值

var fac[mx] int // 阶乘
var invF[mx] int // 阶乘的逆元 invF[i] = invF[i+1] * (i + 1) 
var p2[mx] int // 记录 2 的幂次
var p5[mx] int // 记录 5 的幂次

func init() {
	fac[0] = 1
	for i := 1; i < mx; i++ {
        e2 := bits.TrailingZeros(uint(i)) 
        x := i >> e2

        e5 := 0
        for x % 5 == 0 {
            e5++ 
            x /= 5
        }

		fac[i] = x * fac[i-1] % MOD
        p2[i] = p2[i-1] + e2 
        p5[i] = p5[i-1] + e5 
	}

	invF[mx-1] = power(fac[mx-1], 3) // 使用欧拉定理计算-1 次方（逆元）
	for i := mx-1; i > 0; i-- {
        e2 := bits.TrailingZeros(uint(i)) 
        x := i >> e2

        e5 := 0
        for x % 5 == 0 {
            e5++ 
            x /= 5
        }

		invF[i-1] = invF[i] * x % 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
	}

    // n! * (m!)^-1 * ((n - m)!)^-1
	return fac[n] * invF[m] % MOD * invF[n - m] % MOD * power(2, p2[n] - p2[m] - p2[n - m]) % MOD * power(5, p5[n] - p5[m] - p5[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