题解 | 【模板】组合数

import java.io.*;

public class Main {
    // 定义模数常量，用于所有取模运算
    private static final int MOD = 1000000007;
    // 定义最大计算范围常量
    private static final int MAX_N = 500001;
    // 存储阶乘值的数组
    private static long[] fact = new long[MAX_N];
    // 存储阶乘逆元的数组
    private static long[] invFact = new long[MAX_N];

    /**
     * 主方法
     * 处理输入输出，调用预计算和组合数计算方法
     * @param args 命令行参数
     * @throws IOException 可能抛出的IO异常
     */
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 预计算阶乘和逆元
        precompute();
        // 读取测试用例数量
        int T = Integer.parseInt(br.readLine().trim());

        // 处理每个测试用例
        for (int i = 0; i < T; i++) {
            // 读取每行输入并分割
            String[] str = br.readLine().split("\\s+");
            int n = Integer.parseInt(str[0]);
            int m = Integer.parseInt(str[1]);

            // 输出组合数计算结果
            out.println(nCr(m, n));
        }

        // 清空输出缓冲区并关闭资源
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 使用快速幂算法计算base的exp次方对MOD取模的结果
     * 快速幂算法是一种高效计算幂运算的算法，时间复杂度为O(log n)
     *
     * @param base 底数
     * @param exp  指数
     * @return base的exp次方对MOD取模的结果
     */
    private static long mypower(long base, long exp) {

        // 初始化结果为1对MOD取模，防止MOD为1时结果错误
        long ans = 1 % MOD;
        // 当指数exp大于0时继续循环
        while (exp > 0) {

            // 如果当前指数是奇数，将base乘入结果
            if (exp % 2 == 1) {
                ans = (ans * base) % MOD;
            }

            // base平方，指数减半
            base = (base * base) % MOD;
            exp /= 2;
        }

        // 返回最终结果
        return ans;
    }

    /**
     * 预计算阶乘和阶乘的逆元数组
     * 使用动态规划方法计算阶乘数组fact[]
     * 使用费马小定理计算逆元数组invFact[]
     */
    private static void precompute() {
        // 初始化0的阶乘和0的阶乘逆元为1
        fact[0] = 1;
        invFact[0] = 1;
        // 动态规划计算阶乘数组
        for (int i = 1; i < MAX_N; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        // 使用费马小定理计算最大阶乘的逆元
        invFact[MAX_N - 1] = mypower(fact[MAX_N - 1], MOD - 2);

        // 逆向递推计算其他阶乘的逆元
        for (int i = MAX_N - 2; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    /**
     * 计算组合数 nCr，即从n个物品中选取r个物品的组合数
     * 使用预计算阶乘和阶乘逆元的方法来高效计算组合数
     *
     * @param n 总物品数
     * @param r 选取物品数
     * @return 组合数结果，对MOD取模
     */
    private static long nCr(int n, int r) {
        // 如果r小于0或大于n，组合数为0
        if (r < 0 || r > n) {
            return 0;
        }

        // 使用公式 nCr = n! / (r! * (n-r)!) 计算
        // 通过预计算的阶乘数组fact和阶乘逆元数组invFact来计算
        // 并对MOD取模，防止数值溢出
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }
}