BISHI71 人员分组问题

思路

这题就是个组合问题，本质上是求C(n,5)+C(n,6)+C(n,7)的问题。

求解代码

// 定义模数常量，用于所有取模运算privatestaticfinalintMOD=1000000007;// 定义最大计算范围常量privatestaticfinalintMAX_N=1000001;// 存储阶乘值的数组privatestaticlong[]fact=newlong[MAX_N];// 存储阶乘逆元的数组privatestaticlong[]invFact=newlong[MAX_N];publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 预计算阶乘和逆元precompute();intn=Integer.parseInt(br.readLine().trim());longans=(nCr(n,5)+nCr(n,6)+nCr(n,7))%MOD;out.println(ans);// 清空输出缓冲区并关闭资源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;}