組合數C(n,m)計算優化：避免階乘溢出的乘法公式與動態規劃

直接計算階乘的弊端

`n!` 增長極快，`20!` 已超出 64 位整數範圍 (`~2.4e18`)，`double` 精度也不足。直接算 `n! / m! / (n-m)!` 極易溢出或精度損失。

優化一：乘法迭代公式 (推薦，O(m) 時間 O(1) 空間)

利用組合數定義化簡：

$$ C(n,m) = \frac{n \times (n-1) \times \dots \times (n-m+1)}{m \times (m-1) \times \dots \times 1} = \prod_{i=1}^{m} \frac{n-m+i}{i} $$

**關鍵技巧**：**先乘後除**，每步保證整除，中間結果始終為整數，不產生浮點誤差。

代碼實現 (長整型/BigInteger)

// C++ long long 版 (n <= 60 安全)
long long comb(int n, int m) {
    if (m > n - m) m = n - m; // 優化：取較小的 m
    long long res = 1;
    for (int i = 1; i <= m; ++i) {
        res = res * (n - m + i) / i; // 先乘後除，保證整除
    }
    return res;
}

// Java BigInteger 版 (任意大 n)
BigInteger comb(int n, int m) {
    if (m > n - m) m = n - m;
    BigInteger res = BigInteger.ONE;
    for (int i = 1; i <= m; i++) {
        res = res.multiply(BigInteger.valueOf(n - m + i))
                 .divide(BigInteger.valueOf(i)); // 整除
    }
    return res;
}

優化二：帕斯卡三角動態規劃 (適合多次查詢小 n)

遞推公式：$C(n,m) = C(n-1,m-1) + C(n-1,m)$，邊界 $C(n,0)=C(n,n)=1$。

預計算二維表 `C[MAX_N][MAX_N]`，查詢 O(1)。空間可優化為一維滾動數組。

代碼示例

// C++ 一維滾動數組 O(n^2) 預計算, O(1) 查詢
const int MAX_N = 1000;
vector C(MAX_N + 1, 0);
C[0] = 1;
for (int i = 1; i <= MAX_N; ++i) {
    for (int j = i; j >= 1; --j) { // 逆序更新，避免覆蓋
        C[j] = (C[j] + C[j-1]) % MOD; // 若需取模
    }
}
// 查詢 C(n,m) 即 C[m] (需注意多組查詢時重新計算或存二維表)

場景選擇建議

參考資源

更多優化細節（如質因子分解法、Lucas 定理取模）可參考：組合數計算綜合優化指南