大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6,p必须为素数
2024-08-29 06:04:04
typedef long long ll; /**********************************
大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6,p必须为素数
输入:C(n,m)%p 调用lucas(n,m,p)
复杂度:min(m,p)*log(m)
***********************************/ //ax + by = gcd(a,b)
//传入固定值a,b.放回 d=gcd(a,b), x , y
void extendgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==){d=a;x=;y=;return;}
extendgcd(b,a%b,d,y,x);
y-=x*(a/b);
} //Ax=1(mod M),gcd(A,M)==1
//输入:10^18>=A,M>=1
//输出:返回x的范围是[1,M-1]
ll GetNi(ll A,ll M)
{
ll rex=,rey=;
ll td=;
extendgcd(A,M,td,rex,rey);
return (rex%M+M)%M;
} ll C(ll n,ll m,ll p)
{
if(m>n) return ;
ll up=,dn=;
for(int i=;i<m;i++)
{
up = up*(n-i)%p;
dn = dn*(i+)%p;
}
return up*GetNi(dn, p)%p;
} ll lucas(ll n,ll m,ll p)
{
if(m==) return ;
return C(n%p,m%p,p)*lucas(n/p,m/p,p) % p;
}
最新文章
- ArchLinux+Win10双系统的Grub配置
- yum提示This system is not registered with RHN.RHN support will be disabled.
- TStringList TMemo Text与Add赋值的区别 Memo.Text赋值高度注意事项,不得不知的技巧。
- 【kd-tree】bzoj1941 [Sdoi2010]Hide and Seek
- GPUImage学习
- Hello Indigo
- arcgis python 获得所有的工具名称
- DS1302-演示代码
- hdu 1210_(逻辑训练)
- SQL2-子查询、join查询
- 路由页面缓存开启 以及 keep-alive 给你埋下的坑
- 解决VM安装VMTools后错误提示,实现文件共享
- canvas实现倒计时效果示例(vue组件内编写)
- vsftpd.configro
- svg 动画 透明度 放大缩小 x轴Y轴
- MapServer Tutorial——MapServer7.2.1教程学习——第一节用例实践:Example1.2 Static Map with Two Layers
- Excel与minitab的不同
- 在Mac OS X上用Fluid把网页变成本地App
- hdu 1217 Arbitrage (最小生成树)
- spark SQL概述
热门文章
- docker 安装nginx并挂载配置文件和www目录以及日志目录
- Ubuntu system zabbix-server-3.x install documentation
- ARCGIS FLEX API加载google地图、百度地图、天地图(转)
- 13 Basic Cat Command Examples in Linux
- 【共享单车】—— React后台管理系统开发手记:AntD Table高级表格
- 倍福TwinCAT(贝福Beckhoff)基础教程2.2 TwinCAT常见类型使用和转换_指针
- js - 正斜杆网址转换
- JUnit编写单元测试代码注意点小结
- Eclipse更改默认工作环境编码为UTF-8(9.6)
- SSH框架整合时,如果某一个action提交请求时数据校验失败,后续请求全部失败