lucas数论

2019-08-16 07:42:53来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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;    
View Code

注意事项:{

  (1)能mod即mod

    代码中主要为相乘运算

    很容易爆long long

  (2)特判:

    m==0 return 1;

    n<m return 0;

  (3)lucas细节

    只有当

    n>mod||m>mod 才有lucas    

}

最后

逆元建议线性推

本人太懒

拿了快速幂取模凑数


原文链接:https://www.cnblogs.com/2018hzoicyf/p/11112804.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:超级简单的跨平台高性能音视频播放框架QtAv编译指南

下一篇:C++ 数组输出