组合数学中的常见定理&组合数的计算&取模
2024-09-26 20:57:54
组合数的性质:
C(n,m)=C(n,n-m);
C(n,m)=n!/(m!(n-m)!);
组合数的递推公式:
C(n,m)= C(n-1,m-1)+C(n-1,m);
组合数一般数值较大,题目会要求取模;而求组合数的过程中一般会用到除法,所以会涉及除法取模的知识;
在除法取模的过程中,一般会求一个乘法逆元;
乘法逆元的定义:满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元;
求乘法逆元的方法:
(b/a)modp;(a|b)p为质数;
1.欧拉定理或者费马小定理:
费马小定理是欧拉定理的特殊情况;
费马小定理的定义及证明:链接
由得b/a=(b/a)*(ap-1modp)=b/a*ap-1modp=b*ap-2modp;
除法就被消去了;
而这样做还有一个问题就是p-2一般很大,(因为p一般都取1e9+7,NND,我记得有次BC的题是1e8+7直接把我坑惨了);这时就用快速幂求啦;
附上快速幂的模板:
ll fsat_pow(ll a,ll b)
{
ll s=,base=a;
while(b)
{
if(b&)
{
s*=base;
s%=mod;
}
base*=base;
base%=mod;
b=(b>>);
}
return s;
}
2.扩展欧几里得算法:
当n,m都很大不能一个一个数相乘得到时,这时就需要Lucas定理了;(有心情有时间再来写)
最新文章
- 【原】nodejs全局安装和本地安装的区别
- 关于分布式事务的一个误解:使用了TransactionScope就一定会开启分布式事务吗?
- PVANET----Deep but Lightweight Neural Networks for Real-time Object Detection论文记录
- .NET程序优化
- 冲刺阶段 day11
- 读取和写入 文件 (NSFIleManger 与 NSFileHandle)
- java中hashCode()方法的作用
- 项目前端技术-learn
- 华为上机:IP地址转换
- Ui设计哪里有好的素材
- 1A Theatre Square
- vagrant 配置文件简析
- openresty源码剖析——lua代码的执行
- 用VSCode开发一个基于asp.net core 2.0/sql server linux(docker)/ng5/bs4的项目(3)
- 计蒜客NOIP模拟赛(2) D2T3 银河战舰
- Delphi 7中的四种消息框
- c#常用数值范围汇总
- Confluence 6 恢复一个站点有关使用站点导出为备份的说明
- officewebapps 服务器部署问题
- 不包含数据和字母的Webshell