题解 | 【模板】组合数

Java

快速幂、预处理、费马小定理

import java.util.Scanner;

public class Main {
    static int mod=1000000007;
    static long[] fact=new long[500001];//n!
    static long[] invFact=new long[500001];//(n!)^-1 
    static{
        fact[0]=1;
        fact[1]=1;
        for(int i=2;i<500001;i++){
            fact[i]=(fact[i-1]*i)%mod;
        }
        invFact[500000]=pow(fact[500000],mod-2);
        for(int i=500000-1;i>=0;i--){
            invFact[i]=(invFact[i+1]*(i+1))%mod;
        }


    }
    //快速幂
    public static long pow(long a,long b){
        long res=1;
        a=a%mod;
        while(b>0){
            if((b&1)==1){
                res=(res*a)%mod;
            }
            a=(a*a)%mod;
            b/=2;
        }
        return res;


    }
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            
            long ans=(((fact[m]*invFact[n])%mod)*invFact[m-n])%mod;
            System.out.println(ans);


        }
        

    }
}