lucas数论
2019-08-16 07:42:53来源:博客园 阅读 ()
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++ 数组输出
- bzoj3209: 花神的数论题(数位DP) 2019-08-16
- Lucas定理模板 2019-08-16
- kuangbin带你飞---数论基础 2019-05-10
- NOIP复习之1 数学数论 2018-09-18
- BZOJ2118: 墨墨的等式(最短路 数论) 2018-09-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash