lucas定理求组合数模板
lucas定理:
对于求组合数C(n,m)%p,p是素数,若n=a0+a1 p^1+a2 p^2+a3 p^3+…+an p^n,m=b0+b1 p^1+b2 p^2+…bn p^n。
则:C(n,m)=C(a0,b0) C(a1,b1) C(a2,b2) ....C(an,bn)。
代码模板如下:
int C(int a,int b){
if(a<b)return 0;
int p=1,q=1;
for(int i=a,j=1;j<=b;i--,j++){
p=(ll)p*i%mod;
q=(ll)q*j%mod;
}
return (ll)p*qmi(q,mod-2)%mod;//注意,此处用到了费马小定理求逆元
}
int lucas(int a,int b){
if(a<mod&&b<mod)return C(a,b);
return (ll)lucas(a/mod,b/mod)*C(a%mod,b%mod)%mod;
}