Lucas(卢卡斯）定理
2024-10-06 22:25:15
Lucas定理
对于C(m,n)%P（P是质数）这样的问题，可以通过预处理阶乘和阶乘的逆元，来快速计算。但是当m,n大于P时，就不能保证m,n与P互质了，但不互质的情况下，乘法逆元不存在，此时就需要卢卡斯定理来减小m,n的规模，此处证明略去，给出公式：
C(n,m)%P=C(n/P,m/P)*C(n%P,m%P)%P
```C++
ll Lucas(ll n,ll m)
{
if (m==0)
return 1;
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
```
最新文章
- Vagrant 基础全面解析
- abstract与interface的区别
- 反射动态创建不同的Processor
- 错误：没有为扩展名“.html”注册的生成提供程序。
- Android进阶2之APK方式换肤
- NSDateFormatter 格式说明
- //NSUserDeafult 图片的保存与读取
- IOS中http请求使用cookie
- ubuntu 安装 GCC 和 G++ C++ 开发环境
- uml 图学习记录
- CSS3 水平翻转
- HTML中select的option设置selected="selected"无效的解决方案
- 53. Maximum Subarray最大子序和
- Beta阶段——第5篇 Scrum 冲刺博客
- 关于scratch导出的flash画质很差的问题解决方案
- Jfinal QuartzPlugin 简单使用案例
- November 14th, 2017 Week 46th Tuesday
- Android adb录制视频和截屏的dos脚本
- linux两个线程
- （一）利用 mdb 调试获取 nvlist_t 中 nvpair_t(name/value) 对