组合数的计算方法

组合数：从 $n$ 个不同元素中取出 $m(m≤n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。计算公式为：
$C(n,m)=n!/((n-m)!\times m!), \text{where}\ m\leq n$

性质1： $C(n,m)= C(n,n-m)$
性质2： $C(n,m)=C(n-1,m-1)+C(n-1,m)$

第一种方法：打表

根据性质2直接构建一个 $n\times n$ 的矩阵进行计算：

public class Template {
    static int mod = (int) 1e9 + 7;
    static int max = 110;
    static long[][] com = new long[max][max];

    public static void main(String[] args) {
        int n = 100, m = 30;
        for (int i = 0; i < max; i++) {
            com[i][0] = com[i][i] = 1;
            for (int j = 1; j < i; j++) {
                com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % mod;
            }
        }
        System.out.println(com[n][m]);
    }
}

空间复杂度： $O(n^2)$

预处理时间复杂度： $O(n^2)$ ，查询时间复杂度： $O(1)$

第二种方法：阶乘无模

根据组合的组合数的计算公式 $C(n,m)=n!/((n-m)!\times m!)$ 进行：

public class Template {
    static int mod = (int) 1e9 + 7;
    static int max = 110;
    static long[] fac = new long[max];

    public static void main(String[] args) {
        int n = 20, m = 10;
        fac[0] = 1;
        for (int i = 1; i < max; i++) {
            fac[i] = (fac[i - 1] * i);
        }
        System.out.println(fac[n] / fac[m] / fac[n - m]);
    }
}

空间复杂度： $O(n)$

预处理时间复杂度： $O(1)$ ，查询时间复杂度： $O(n)$

由于涉及除法，无法直接取模，所以引入乘法逆元。

第三种方法：乘法逆元

逆元：对于 $a$ 和 $p$ （ $a$ 和 $p$ 互素），若 $a*b\%p\equiv1$ ，则称 $b$ 的最小正整数解为 $a%p$ 的逆元。

当求解 $(a/b)\%p$ ，如果知道 $b\%p$ 的逆元为 $c$ ，那么可以转化为 $(a/b)\%p=a*c\%p=(a\%p)(c\%p)\%p$ 。暴力做法：

public class Template {
    static int mod = (int) 1e9 + 7;
    static int max = 110;
    static long[] fac = new long[max];
    static long[] inv = new long[max];

    public static void main(String[] args) {
        int n = 100, m = 30;
        inv[0] = fac[0] = 1;
        for (int i = 1; i < max; i++) {
            fac[i] = (fac[i - 1] * i) % mod;
            inv[i] = inv(fac[i]);
        }
        System.out.println(((fac[n] * inv[m]) % mod * inv[n - m]) % mod);
    }

    public static long inv(long a) {
        for (int x = 1; x < mod; x++) {
            if (a * x % mod == 1) return x;
        }
        return 0;
    }
}

空间复杂度： $O(n)$

预处理时间复杂度： $O(p)$ ，其中 $p=mod$ ，查询时间复杂度： $O(1)$

第四种方法：乘法逆元+快速幂+阶乘

费马小定理：对于a和素数p，满足 $a^{p-1}\%p\equiv 1$ 。

因为 $a^{p-1}=a^{p-2}*a$ ，所以有 $a^{p-2}*a\%p\equiv 1$ 。根据逆元的定义可知， $a^{p-2}$ 是 $a$ 的逆元。因此可以将求解逆元的问题转换为 $a^{p-2}$ 的快速幂问题。

public class Template {
    static int mod = (int) 1e9 + 7;
    static int max = 110;
    static long[] fac = new long[max];
    static long[] inv = new long[max];

    public static void main(String[] args) {
        int n = 100, m = 30;
        inv[0] = fac[0] = 1;
        for (int i = 1; i < max; i++) {
            fac[i] = (fac[i - 1] * i) % mod;
            inv[i] = inv(fac[i]);
        }
        System.out.println(((fac[n] * inv[m]) % mod * inv[n - m]) % mod);
    }

    public static long pow(long a, long b) {
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) ans = (ans * a) % mod;
            a = a * a % mod;
            b = b >> 1;
        }
        return ans;
    }

    public static long inv(long a) {
        return pow(a, mod - 2);
    }
}

空间复杂度： $O(n)$

预处理时间复杂度： $O(\log p)$ ，其中 $p=mod$ ，查询时间复杂度为 $O(1)$