資料范圍較大， a,b都是1e5
直接根據公式預處理
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); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93565.html
標籤：其他
上一篇：885.求組合數 I（模板）