思路求解代码// 定义模数常量用于所有取模运算privatestaticfinalintMOD1000000007;// 定义最大计算范围常量privatestaticfinalintMAX_N500001;// 存储阶乘值的数组privatestaticlong[]factnewlong[MAX_N];// 存储阶乘逆元的数组privatestaticlong[]invFactnewlong[MAX_N];/** * 主方法 * 处理输入输出调用预计算和组合数计算方法 * param args 命令行参数 * throws IOException 可能抛出的IO异常 */publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入PrintWriter输出结果BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));PrintWriteroutnewPrintWriter(newOutputStreamWriter(System.out));// 预计算阶乘和逆元precompute();// 读取测试用例数量intTInteger.parseInt(br.readLine().trim());// 处理每个测试用例for(inti0;iT;i){// 读取每行输入并分割String[]strbr.readLine().split(\\s);intnInteger.parseInt(str[0]);intmInteger.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取模的结果 */privatestaticlongmypower(longbase,longexp){// 初始化结果为1对MOD取模防止MOD为1时结果错误longans1%MOD;// 当指数exp大于0时继续循环while(exp0){// 如果当前指数是奇数将base乘入结果if(exp%21){ans(ans*base)%MOD;}// base平方指数减半base(base*base)%MOD;exp/2;}// 返回最终结果returnans;}/** * 预计算阶乘和阶乘的逆元数组 * 使用动态规划方法计算阶乘数组fact[] * 使用费马小定理计算逆元数组invFact[] */privatestaticvoidprecompute(){// 初始化0的阶乘和0的阶乘逆元为1fact[0]1;invFact[0]1;// 动态规划计算阶乘数组for(inti1;iMAX_N;i){fact[i](fact[i-1]*i)%MOD;}// 使用费马小定理计算最大阶乘的逆元invFact[MAX_N-1]mypower(fact[MAX_N-1],MOD-2);// 逆向递推计算其他阶乘的逆元for(intiMAX_N-2;i1;i--){invFact[i](invFact[i1]*(i1))%MOD;}}/** * 计算组合数 nCr即从n个物品中选取r个物品的组合数 * 使用预计算阶乘和阶乘逆元的方法来高效计算组合数 * * param n 总物品数 * param r 选取物品数 * return 组合数结果对MOD取模 */privatestaticlongnCr(intn,intr){// 如果r小于0或大于n组合数为0if(r0||rn){return0;}// 使用公式 nCr n! / (r! * (n-r)!) 计算// 通过预计算的阶乘数组fact和阶乘逆元数组invFact来计算// 并对MOD取模防止数值溢出return(((fact[n]*invFact[r])%MOD)*invFact[n-r])%MOD;}