一、组合数的定义
组合数是数学中的一个概念，用于计算从n个不同元素中，任取k个元素的不同组合数，用C(n,k)表示。可以用以下公式计算：
C(n,k)= n! / (k!*(n-k)!);
其中，n!表示n的阶乘，即n*(n-1)*(n-2)*…*1, 0!=1。
二、暴力枚举法
最朴素的方法是通过暴力枚举所有可能的组合情况，然后计算符合要求的组合数。这种方法的时间复杂度为O(C(n,k))，在k或n较大时其效率极低。
代码示例：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int ans=0;
for(int i=0;i<(1<<n);i++){ //枚举所有情况
if(__builtin_popcount(i)==k) ans++; //统计符合要求的情况数
}
cout<<ans<<endl;
return 0;
}
三、递推法
通过C(n,k)=C(n-1,k-1)+C(n-1,k)的递推公式，可以通过存储上一步计算的结果来计算当前步的结果。这种方法的时间复杂度为O(k*(n-k))，效率相较于暴力枚举有所提高。
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int c[maxn][maxn];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i) c[i][j]=1; //边界条件
else c[i][j]=c[i-1][j-1]+c[i-1][j]; //递推公式
}
}
cout<<c[n][k]<<endl;
return 0;
}
四、Lucas定理
当n和k均比较大时，使用暴力枚举和递推都不太现实。可以使用Lucas定理，将n和k分解为p进制数的形式，进而计算组合数。时间复杂度为O(logp(n)+logp(k))，其中p为模数。
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int mod=10007; //取模数
int fac[maxn],inv[maxn]; //预处理阶乘和逆元
int power(int a,int b,int m){ //快速幂
int ans=1%m;
while(b>0){
if(b&1) ans=(ans*a)%m;
a=(a*a)%m;
b>>=1;
}
return ans;
}
int C(int n,int k,int m){ //计算组合数
if(n0&&k>0){ //每次取p进制数的最后一位进行计算，直至n=0或k=0
int a=n%m;
int b=k%m;
if(a<b) return 0;
ans=(ans*C(a,b,m))%m;
n/=m;
k/=m;
}
return ans;
}
int main(){
fac[0]=1;
for(int i=1;i=0;i--) inv[i]=(inv[i+1]*(i+1))%mod;
int n,k;
cin>>n>>k;
cout<<Lucas(n,k,mod)<<endl;
return 0;
}
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/183140.html
微信扫一扫 
支付宝扫一扫 