组合数算法

前一段时间笔试遇到了好几次组合数的题目（当然也可能其实是用动态规划去做），笔试时看着算法超时有一种深深的无力感。最近有空收集了一点组合数计算的算法，算是以一个非竞赛选手的视角去描述这些算法（公式证明什么的就算了，主要负责用）。

递推式预处理

原理

组合数递推公式： $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$

算法复杂度

空间复杂度
- 打表 $\Omicron(nm)$
时间复杂度
- 预处理 $\Omicron(nm)$
- 单次查询 $\Omicron(1)$

示例代码

Java
class CombinationPrecompute {
    static final int N = 1000; // 根据需要设定最大 n
    static long[][] C = new long[N + 1][N + 1];
    static final long MOD = 1_000_000_007; // 如果需要取模，可以加上；否则去掉 MOD 相关代码

    // 预处理组合数表
    static {
        for (int i = 0; i <= N; i++) {
            C[i][0] = 1; // C(i,0) = 1
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
            }
        }
    }

    // 查询组合数 C(n, m)
    public static long comb(int n, int m) {
        if (m < 0 || m > n) return 0;
        return C[n][m];
    }
    
    public static void main(String[] args) {
        System.out.println(comb(5, 2)); // 输出 10
        System.out.println(comb(10, 3)); // 输出 120
    }
}

预处理阶乘+逆元（模 p 意义下）

原理

组合数公式： $C_n^m=\frac{n!}{m!(n-m)!}$
费马小定理： $a^{p-1} \equiv 1\pmod{p}$ （ $p$ 是素数）
- 两边同除 $a$ 得
- $a^{p-2} \equiv \frac{1}{a}\pmod p$
- $\bmod\,p$ 意义下 $\frac{1}{a}$ 就是 $a$ 的逆元， $\operatorname{inv}(a)=a^{p-2}$
- $a^{p-2}$ 可用快速幂计算求得（时间复杂度 $\log{p}$ ）

算法复杂度

空间
- 打表 $\Omicron(n)$
时间
- 预处理阶乘 $\Omicron(n)$
- 预处理逆元 $\Omicron(n)$
- 单次查询 $\Omicron(\log{p})$
- 若预处理逆元，则单次查询为 $\Omicron(1)$

Lucas 定理

Lucas 定理是用于处理组合数取模的定理。通常用于解决阶乘无法解决的问题。适用于 $n$ 较大（ $n\ge 10^9$ ），p 较小（ $p\le 10^5$ ）的情况。

原理

Lucas 定理： $C_n^m \bmod p=C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n \bmod p}^{m \bmod p} \bmod p$

算法复杂度

空间
- 预处理阶乘和阶乘的逆元 $\Omicron(p)$
时间
- 预处理 $\Omicron(p)$
- 单次查询 $\Omicron(\log{n})$

示例代码

以洛谷 P3807 为例，针对 $p$ 以内的组合数我们打一个表，用阶乘和阶乘逆元 $\Omicron(n)$ 的递推公式去加快 $C_{n \bmod p}^{m \bmod p} \bmod p$ 项的计算。

Java
import java.io.*;
import java.util.*;
public class Main {
    static final int P = 100003;
    static long[] fact = new long[P];
    static long[] invFact = new long[P];

    static long pow(long a, long b, int p) {
        long res = 1;
        a %= p;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }

    static void init(int p) {
        fact[0] = 1;
        for (int i = 1; i < p; i++) {
            fact[i] = fact[i - 1] * i % p;
        }
        invFact[p - 1] = pow(fact[p - 1], p - 2, p);
        for (int i = p - 2; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % p;
        }
    }

    static long comb(int n, int m, int p) {
        if (n < m) return 0;
        return fact[n] * invFact[m] % p * invFact[n - m] % p;
    }

    static long lucas(long n, long m, int p) {
        if (m == 0) return 1;
        return comb((int)(n % p), (int)(m % p), p) * lucas(n / p, m / p, p) % p;
    }

    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int T = cin.nextInt();

        for(int i = 0; i < T; i++) {
            int n = cin.nextInt(),   m = cin.nextInt(),  p = cin.nextInt();
            init(p);
            System.out.println(lucas(n + m, n , p));
        }
    }
}

目录

递推式预处理

原理

算法复杂度

示例代码

预处理阶乘+逆元（模 p 意义下）

原理

算法复杂度

Lucas 定理

原理

算法复杂度

示例代码

参考