组合数：从个不同元素中取出个元素的所有组合的个数，叫做从个不同元素中取出个元素的组合数。计算公式为：

• 性质1：
• 性质2：

第一种方法：打表

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

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]);
    }
}

空间复杂度：

预处理时间复杂度：，查询时间复杂度：

第二种方法：阶乘无模

根据组合的组合数的计算公式进行：

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]);
    }
}

空间复杂度：

预处理时间复杂度：，查询时间复杂度：

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

第三种方法：乘法逆元

逆元：对于和（和互素），若，则称的最小正整数解为的逆元。

当求解，如果知道的逆元为，那么可以转化为。暴力做法：

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;
    }
}

空间复杂度：

预处理时间复杂度：，其中，查询时间复杂度：

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

费马小定理：对于a和素数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 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);
    }
}

空间复杂度：

预处理时间复杂度：，其中，查询时间复杂度为