用C++计算组合数的方法和实例

一、组合数的定义

组合数是数学中的一个概念，用于计算从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;
}