887. 求组合数 III(模板 卢卡斯定理)
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
a,b都非常大,但是p较小
前边两种方法都会超时的 N^2 和NlongN
可以用卢卡斯定理 P*longN*longP
定义:
代码:
import java.util.Scanner; public class Main{ static int p; //快速幂 static long quick_pow(long a,long b){ long res=1; while(b>0){ if((b&1)==1) res=res*a%p; a=a*a%p; b>>=1; } return res; } //根据组合数定义求C(a,b) static long C(long a,long b){ long res=1; for(long i=1,j=a;i<=b;i++,j--){ res=res*j%p; res=res*quick_pow(i,p-2)%p; } return res; } //卢卡斯定理 static long lucas(long a,long b){ if(a<p && b<p) return C(a,b); return C(a%p,b%p)*lucas(a/p,b/p)%p; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int t=scan.nextInt(); while(t-->0){ long a=scan.nextLong(); long b=scan.nextLong(); p=scan.nextInt(); System.out.println(lucas(a,b)); } } }
更多精彩