用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;
}