組合數 C(n,m) 高效計算與取模技巧總結

前言

在競賽程式設計中，組合數 C(n, m) 的計算是常見需求。早期嘗試用遞歸實作，非但效率低落，還常因疊代深度導致超時或棧溢位；若涉及取模運算，更需引入模逆元，實作細節稍有不慎便易出錯。為此，本文整理出三種實用模板，涵蓋線性疊代、遞歸定義與模數運算，供後續專案快速引用。

一、線性疊代法：O(m) 時間求 C(n, m)

觀察組合數性質：

C(n, 1) = n / 1
C(n, 2) = C(n, 1) × (n-1) / 2
C(n, 3) = C(n, 2) × (n-2) / 3
……
C(n, m) = C(n, m-1) × (n-m+1) / m

每一步分子分母皆為整數，數學證明保證中間結果必為整數，不會出現小數截斷問題。利用此遞推關係，只需單層迴圈即可在 O(m) 時間內完成計算。

long long combine_linear(long long n, long long m) {
    long long res = 1;
    for (long long i = 1, j = n; i <= m; ++i, --j) {
        res = res * j / i;   // 整數除法，順序不可交換
    }
    return res;
}

優點：極簡、快速、無溢位風險（前提是最終結果在 long long 範圍內）。
缺點：不適用於需取模的場景，因整數除法在模數意義下不成立。

二、遞歸定義法：直觀但極慢

根據帕斯卡恆等式 C(n, m) = C(n-1, m-1) + C(n-1, m) 直接遞歸：

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

測試發現，C(50, 25) 已嚴重超時，指數級複雜度使其僅適合教學演示，實戰請避免使用。

三、線性疊代配合模逆元：求 C(n, m) % mod

當模數 mod 為質數時，可用費馬小定理或擴展歐幾里得算法求模逆元。下方採用擴展 GCD 實作 inv(a, mod)，再將線性疊代中的除法替換為乘逆元：

// 擴展歐幾里得求逆元
void ex_gcd(long long a, long long b, long long &d, long long &x, long long &y) {
    if (!b) { d = a; x = 1; y = 0; }
    else { ex_gcd(b, a % b, d, y, x); y -= x * (a / b); }
}

long long mod_inv(long long a, long long mod) {
    long long d, x, y;
    ex_gcd(a, mod, d, x, y);
    return d == 1 ? (x + mod) % mod : -1;  // 互質才存在逆元
}

// 線性疊代 + 取模
long long combine_mod(long long n, long long m, long long mod) {
    long long res = 1;
    for (long long i = 1, j = n; i <= m; ++i, --j) {
        res = res * j % mod * mod_inv(i, mod) % mod;
    }
    return res;
}

注意：mod 必須為質數，否則部分 i 可能與 mod 不互質，導致逆元不存在。若 mod 非質數，需改用質因數分解 + 中國剩餘定理或 Lucas 定理等進階技巧。

總結對照表

將上述三個函數封裝為工具類或頭檔，即可在比賽或專案中「複製貼上」即用，避免重複造輪子。