組合數 C(n,m) 計算全攻略：線性遞推、遞歸與取模逆元

組合數 C(n,m) 計算全攻略：線性遞推、遞歸與取模逆元

組合數計算是算法競賽高頻需求。本文總結三種計算方法：線性遞推（O(m)）、遞歸定義（指數級）、取模情況下的模逆元法，並提供可直接使用的 C++ 模板代碼。

方法一：線性遞推法 —— 推薦通用做法

利用遞推關係：C(n,k) = C(n,k-1) * (n-k+1) / k
從 C(n,0)=1 開始，迭代計算至 C(n,m)。每步乘除順序保證整除，無小數誤差。

long long combine1(long long n, long long m) {
    long long sum = 1;
    for(long long i = 1, j = n; i <= m; i++, j--)
        sum = sum * j / i; // 先乘後除，保證整數運算
    return sum;
}

優點：O(m) 時間，O(1) 空間，無溢出風險（若結果在範圍內）。
證據：C(10,4) = (((10/1)*9/2)*8/3)*7/4 = 210

方法二：遞歸定義法 —— 僅適合小數據

基於帕斯卡恆等式：C(n,m) = C(n-1,m) + C(n-1,m-1)

long long combine2(long long n, long long m) {
    if(n == m || m == 0) return 1;
    return combine2(n-1, m) + combine2(n-1, m-1);
}

缺點：重複計算極多，C(50,25) 即嚴重超時棧溢出，**不推薦實戰使用**。

方法三：取模情況下的線性計算 —— 模逆元法

需計算 C(n,m) % mod，其中 mod 為質數。利用費馬小定理求模逆元：a^(mod-2) % mod 為 a 的逆元。

// 快速冪求 a^b % mod
long long mod_pow(long long a, long long b, long long mod) {
    long long ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

// 模逆元（mod 為質數）
long long inv(long long a, long long mod) {
    return mod_pow(a, mod-2, mod);
}

// 取模組合數
long long combine_mod(long long n, long long m, long long mod) {
    long long sum = 1;
    for(long long i = 1, j = n; i <= m; i++, j--)
        sum = sum * j % mod * inv(i, mod) % mod;
    return sum;
}

擴展歐幾里得求逆元（通用，mod 不必為質數）

void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {
    if(!b) { d = a; x = 1; y = 0; }
    else { exgcd(b, a%b, d, y, x); y -= x * (a/b); }
}

long long inv_exgcd(long long a, long long mod) {
    long long d, x, y;
    exgcd(a, mod, d, x, y);
    return d == 1 ? (x + mod) % mod : -1; // 互質才有逆元
}

性能對比與選擇建議

實戰模板建議

競賽中推薦攜帶 線性遞推 + 快速冪模逆元 兩套模板。注意 long long 範圍（~9e18），大數需用高精度或 Python。