lucas数论

来自perm排列计数的悲伤

 

lucas说过

c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)%p

于是乎

在好记的情况下没有搞原理证明

导致permwa了一上午

 1 ll pow(ll a,ll b){
 2     ll ans=1;
 3     while(b){
 4         if(b&1)ans=(ans*a)%p;
 5         a=(a*a)%p;
 6         b>>=1;
 7     }
 8     return ans%p;
 9 }
10 ll c(int a,int b){
11     if(a<b)return 0;
12     if(b==0)return 1;
13     return jc[a]*pow(jc[a-b]*jc[b]%p,p-2)%p;
14 }
15 ll lucas(int a,int b){
16     if(b>a)return 0;
17     if(b==0)return 1;
18     if(a>p||b>p)return c(a%p,b%p)*lucas(a/p,b/p)%p;
19     return c(a,b)%p;
20 }
21         jc[0]=1;
22     for(int i=1;i<=n;++i)jc[i]=jc[i-1]*1ll*i%p;    

注意事项：{

　　（1）能mod即mod

　　　　代码中主要为相乘运算

　　　　很容易爆long long

　　（2）特判：

　　　　m==0 return 1;

　　　　n<m return 0;

　　（3）lucas细节

　　　　只有当

　　　　n>mod||m>mod 才有lucas　　　　

}

最后

逆元建议线性推

本人太懒

拿了快速幂取模凑数