BISHI70 【模板】组合数

思路

求解代码

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