c++中如何实现组合数计算_c++计算排列组合C(n,k)的方法【实例】

推荐用迭代乘除法计算组合数：先取min(k, n−k)，再边乘边除，用unsigned long long避免溢出和浮点误差，边界判断确保k∈[0,n]，n>170时std::tgamma会溢出，不适用。

直接用 std::tgamma 计算组合数容易出错

很多人第一反应是套公式 C(n,k) = n! / (k! × (n−k)!)，再用 std::tgamma(n+1) 算阶乘。但这是危险的：浮点误差在 n > 17 时就明显，n > 170 会溢出为 inf，且 tgamma 对非整数输入无定义。实际项目中不推荐。

用迭代乘除法避免大数和溢出

核心思路是把 C(n,k) 展开为 k 项连乘再连除：C(n,k) = (n × (n−1) × … × (n−k+1)) / (1 × 2 × … × k)，边乘边除，控制中间值始终在 long long 范围内（只要最终结果 ≤ 2⁶³−1）。

• 先取 min(k, n−k) 替换 k —— 利用 C(n,k) = C(n,n−k) 减少循环次数
• 用 unsigned long long 存中间结果，更安全
• 每步都做整除，确保不累积浮点误差

unsigned long long combination(int n, int k) {     if (k < 0 || k > n) return 0;     if (k == 0 || k == n) return 1;     k = std::min(k, n - k);     unsigned long long res = 1;     for (int i = 1; i <= k; ++i) {         res = res * (n - k + i) / i;     }     return res; }

需要支持大 n？考虑模意义下的组合数

当 n 达到 1e5 或更大，且题目要求结果对某个质数（如 1e9+7）取模时，就不能用上面的迭代法——除法要转成乘逆元。此时预处理阶乘及其逆元是标准做法：

• 预计算 fac[i] = i! mod MOD，O(n)
• 用快速幂或线性递推求 inv_fac[n]，再倒推所有 inv_fac[i]
• C(n,k) ≡ fac[n] * inv_fac[k] % MOD * inv_fac[n-k] % MOD

注意：该方法仅适用于 MOD 是质数、且 n

立即学习“C++免费学习笔记（深入）”；

边界和类型问题比算法本身更容易翻车

写完函数别急着交，这几个点常被忽略：

• n 和 k 是 int，但中间计算可能溢出 —— 必须用 unsigned long long 接收乘积
• 输入可能为负或 k > n，返回 0 比崩溃更合理
• 某些 OJ 编译器（如 MinGW）下 std::min 对 int 和 unsigned 混用会报警，显式转成同类型
• 如果真要算 n=1000 以上的精确值，long long 不够，得上 boost::multiprecision::cpp_int 或手写高精度

组合数看着简单，但溢出、类型转换、边界判断这三块，占了实际调试时间的八成以上。