886. 求组合数 II(模板) 算法 第1张

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

  数据范围较大, a,b都是1e5

  直接根据公式预处理

 886. 求组合数 II(模板) 算法 第2张

 

   886. 求组合数 II(模板) 算法 第3张 1/i就是求i的逆元(逆元求法:mod为质数,逆元就是 i^(mod-2)%mod )

   O(N*logN)

 

import java.util.Scanner;

public class Main{
        static final int N=100005;
        static final int mod=(int)1e9+7;
        static long fact[]=new long[N];
        static long infact[]=new long[N];
        static long quick_pow(long a,long b){
                long res=1;
                while(b>0){
                        if((b&1)==1) res=res*a%mod;
                        a=a*a%mod;
                        b>>=1;
                }
                return res%mod;
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                fact[0]=infact[0]=1;
                for(int i=1;i<N;i++){
                        fact[i]=fact[i-1]*i%mod;
                        infact[i]=infact[i-1]*quick_pow(i,mod-2)%mod;
                }
               int t=scan.nextInt();
               while(t-->0){
                           int a=scan.nextInt();
                           int b=scan.nextInt();
                           System.out.println(fact[a]*infact[a-b]%mod*infact[b]%mod);
               }
        }
}

 

 

   

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄