求组合数常用的方法
方法 常用 组合
2023-09-11 14:19:53 时间
求C(n,m) //其中n>=m
一、暴力
1.按定义直接计算:
n,m<15
long long的大小制约着n,m,如果加上mod,n,m可以再高些。
ll C(int n,int m) //暴力
{
if(n>m) return 0;
if(n<m-n) n=m-n;
ll ans=1;
for(int i=n+1;i<=m;i++) ans*=i;
for(int i=1;i<=m-n;i++) ans/=i;
return ans;
}
2.二维数组打表:
n,m<5000
通过递推公式实现:com[i][j]=com[i-1][j]+com[i-1][j-1];
#define ll long long
#define M 5000
ll com[M][M];
void Prons()
{
com[0][1]=1;
for(int i=1;i<M;i++) //i>j
for(int j=0;j<=i;j++){
if(j==0) com[i][j]=1;
else com[i][j]=com[i-1][j]+com[i-1][j-1];
}
}
特点:优点是简单短,缺点是时间慢,范围小
二、利用快速幂
3.快速幂+逆元
n,m<1e6
仍然是利用 C(n,m)=n!/[m!*(n-m)!] 的计算,预处理阶乘数组降低时间,qpow是逆元
ll fac[1000005]; //阶乘
void init(){
fac[0]=1;
for(int i=1;i<1e6;i++)
fac[i]=(fac[i-1]*i)%mod;
}
ll qpow(ll a,ll b)
{
ll ans=1;
a%=mod;
while(b){
if(b&1){
ans=ans*a%mod;
b--;
}
b>>= 1;
a=a*a%mod;
}
return ans;
}
ll C(int n,int m){
return fac[n]*qpow(fac[n-m],mod-2)%mod*qpow(fac[m],mod-2)%mod;
}
特点:时间复杂度是log2,如果符合范围,这个是时间最快的。这个也是最好用的
4.卢斯卡定理1:
通过卢思卡公式实现
p为质数 n≤1e18,m≤1e6,mod≤1e9(可以是1e9+7)
#define ll long long
#define M 100005
const ll mod=10007;
ll a,b;
ll qpow(ll a,ll b)
{
ll ans=1;
a%=mod;
while(b)
{
if(b&1)
{
ans=ans*a%mod;
b--;
}
b>>= 1;
a=a*a%mod;
}
return ans;
}
ll C(ll n,ll m)
{
if(m>n) return 0;
ll ans=1;
for(int i=1;i<=m;i++)
{
ll a=(n+i-m)%mod;
ll b=i%mod;
ans=ans*(a*qpow(b,mod-2)%mod)%mod;
}
return ans;
}
ll Lucas(ll n,ll m) //n>m
{
if(m==0) return 1;
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
特点:这个比下面的常用些,mod可以取到1e9+7。
n,m比较大的情况下可以用,如果n,m都<1e6,还是建议用上的面,因为可能会超时。
5.卢斯卡定理2:
m≤n≤1e18,mod≤1e6
#define ll long long
#define M 1000005
ll a,b,mod;
ll f[M];
void init(){
f[0]=1;
for(int i=1;i<=mod;++i)
f[i]=f[i-1]*i%mod;
}
ll qpow(ll a, ll b){
ll ans=1;
a%=mod;
while(b)
{
if(b&1)
{
ans=ans*a%mod;
b--;
}
b>>= 1;
a=a*a%mod;
}
return ans;
}
ll Lucas(ll n,ll k){
ll ret=1;
while(n&&k){
ll nn=n%mod,kk=k%mod;
if(nn<kk) return 0;
ret=ret*f[nn]*qpow(f[kk]*f[nn-kk]%mod,mod-2)%mod;
n/=mod;
k/=mod;
}
return ret;
}
特点:卢斯卡定理适用于n,m超大的情况,但是时间复杂度并不是很好,有两种可供选择。
具体的知识没有相关了解,建议自己去搜搜,本文只做适用范围总结
相关文章
- struts2 s:if标签以及 #,%{},%{#}的使用方法
- Java中lang包的常用方法介绍
- Class.getResource()方法的使用
- 【学习总结】SQL的学习-5-性能调优常用方法介绍与数据导入导出
- Linux下使用rsync最快速删除海量文件的方法
- Java对存储过程的调用方法
- 数据分析方法汇总(2)
- spring boot: 从配置文件中读取数据的常用方法(spring boot 2.3.4)
- python垃圾回收示例及__del__(self)方法的使用(它会在对象被垃圾回收前调用)
- SAP UI5 视图控制器 View Controller 的生命周期方法 - Lifecycle methods
- Android修行手册 - TabLayout全解析(上)-常用方法
- Android native 层的同步方法
- 【Android笔记64】Android之Fragment常用方法介绍及其使用
- ML之FE:特征工程/数据预处理之构造特征之特征分箱/数据分桶的常用六大类方法—基于统计(等距/等频+分位数+标准差/f方差)、基于数据分布(自然断点+重尾分布)、基于评价指标的自适应(卡方/Bes
- 成功解决(不可思议的解决方法)UnicodeDecodeError utf-8 codec cant decode byte 0xd2 in position 3484 invalid con
- ML之FE:特征工程中常用的五大数据集划分方法(留1法/留p法、随机划分法、K折交叉验证法、自定义分割法、特殊类型数据分割法【时间序列数据】、自助采样法)理论讲解及其代码实现
- Py之transformers:transformers的简介、安装、使用方法、案例应用之详细攻略
- CloudNative:云原生(分布式云)的简介(发展&演变/为什么需要/优势&价值/安全/对比传统企业应用)、四大核心技术、CNCF云原生交互景观、云原生技术的使用经验及方法之详细攻略
- 赶紧收藏,年终盘点:绝不仅仅15种最常用的数据分析方法和模型
- python数据分析-pandas常用方法
- 当执行游戏0xc000007b错误的解决方法
- FileSystemWatcher使用方法具体解释
- 如何隐藏、克隆账号及两种排查隐藏账号方法
- python 查询 elasticsearch 常用方法(Query DSL)
- C++中union的使用方法