组合数这玩意儿刷算法题的基本都绕不开。它出现在概率统计、排列组合、动态规划优化甚至游戏里的抽卡概率计算里但很多人一上手写C实现就被溢出、精度、性能这几个问题轮番教育。网上搜“C组合数”能翻出一堆代码但真正讲清楚“什么时候该用哪种方法”的并不多。这篇就把我这些年实际用下来的3种实现方式完整拆一遍从原理到代码从适用边界到踩坑记录一次性说透。先说结论组合数的计算难点从来不是“不知道公式”而是公式直接套进去会发现中间过程溢出、递归层级太深、打表内存爆炸……这些问题比公式本身更值得琢磨。所以这篇不是单纯丢3段代码而是把每种方法背后的设计思路和适用场景讲明白你看完能直接根据自己手头的数据规模选方案而不是对着代码发呆。1. 整体设计思路为什么组合数值得单独讲讲1.1 组合数是什么什么时候要用它组合数的定义很直白从n个不同元素里选k个不考虑顺序有多少种选法。数学上记作C(n, k)或者( n k )公式是C(n, k) n! / (k! * (n - k)!)这个公式人尽皆知但你真去实现一下就会发现坑很多。n20的时候20!大概是2.43e18已经逼近long long的上限9.22e18了n30的时候30!直接到了2.65e32连unsigned long long都装不下。所以“先算阶乘再相除”这种教科书写法在n稍微大一点的时候就完蛋。实际应用中组合数出现的场景非常频繁。比如你在做概率计算的时候要从100个样本里抽5个有多少种组合比如在动态规划里杨辉三角就是组合数的递推形式再比如处理多项式展开、计算二项式系数本质都是在求组合数。所以不是“这个功能偶遇用一下”而是很多算法题的基础工具。1.2 三套方案怎么选一张表看清边界我常用的3种方法分别是公式法、递推法、质因数分解法。它们各有各的适用场景不存在谁完全替代谁。实现方法时间复杂度空间复杂度适用场景安全数据范围以long long输出为例公式法O(k)O(1)单次查询n不大n ≤ 67递推法O(n*k)O(n*k)或O(n)多次查询、批量打表打表边界约n ≤ 1000质因数分解法O(n log n)O(位数)精确计算大结果可高精度输出n可达数万瓶颈在输出位数后面每个方法我都会给出完整代码和边界分析。这里先说一个通用的建议如果你只算一次组合数优先考虑公式法如果同一个n下面要反复查多个k那递推打表才是正道如果n很大而且你要的是精确结果而不是取模后的余数那就得上质因数分解法。1.3 方法选型背后的踩坑历史我最初学的时候先用的是最直观的阶乘实现然后被n21的溢出教做人。后来改用double硬算结果C(100, 50)这种还能看但C(300, 150)开始出现精度丢失输出结果末尾几位全是垃圾数字。再后来学会打表递推又被内存限制卡过——有次想直接开一个5000x5000的long long二维数组一算内存200MB直接爆掉。这些坑让我意识到组合数计算的本质是一个“数据范围管理”问题。不同方法的核心差异不在于公式不同而在于如何控制中间过程的增长幅度。公式法通过“边乘边除”压缩中间结果递推法通过逐层累加避免阶乘爆炸质因数分解法则是把乘除法转化成加减法直接从根源上绕开大数中间量。理解了这层逻辑你才算真正掌握这三种方法。2. 方法一公式法最直观但最需要小心2.1 基础实现与对称性优化公式法的核心就是直接用C(n, k) n! / (k! * (n - k)!)这个定义但绝不是“先算三个阶乘再相除”。正确做法是化简成连乘形式C(n, k) product (n - k i) / i其中i从1到k代码如下#include iostream using namespace std; long long C_formula(int n, int k) { if (k 0 || k n) return 0; // 对称性优化C(n, k) C(n, n-k) // 选择较小的k减少乘法次数降低溢出风险 if (k n - k) k n - k; long long res 1; for (int i 1; i k; i) { res res * (n - k i) / i; } return res; } int main() { cout C_formula(10, 3) endl; // 120 cout C_formula(67, 33) endl; // 大约1.42e19超出long long范围 return 0; }注意到我先做了一步“对称性优化”把k替换成min(k, n-k)。这个替换是有数学依据的C(n, k) C(n, n-k)因为选k个元素和排除n-k个元素是一一对应的。这么做的好处很直接循环次数从k变成了min(k, n-k)乘法次数减少溢出概率也随之下降。2.2 边乘边除的原理为什么每一步都能整除重点讲一下res res * (n - k i) / i这个表达式。很多初学者会怀疑先乘后除res * (n-ki)会不会已经溢出了或者除不尽得到小数怎么办先说整除性问题C(n, k)本身一定是整数而且这个连乘写法有一个性质——每乘一项再除以当前i时结果一定是整数。你可以从组合数的递推性质来理解C(n-ki, i)就是一个整数而res恰好就等于C(n-ki, i)。每一步都在算一个中间组合数当然能整除。再说溢出问题这确实是公式法的最大隐患。即使做了对称性优化long long能安全计算的组合数也有上限。我实测下来n 67、k 33时C(67, 33)约等于1.42e19已经超出long long的最大值9.22e18而C(66, 33)约等于7.2e18还在安全范围内。所以公式法在long long输出场景下n超过66就要高度警惕。2.3 公式法的边界与溢出判断怎么判断某次计算是否溢出了一个实用小技巧是在乘法前后做一次反向校验。long long C_safe(int n, int k) { if (k n - k) k n - k; long long res 1; for (int i 1; i k; i) { long long before res; res res * (n - k i) / i; // 如果乘法使其变小或变负说明溢出 if (res before) { cerr overflow at i i endl; return -1; } } return res; }这种判断方式不完美但对付大部分溢出场景够用。另外如果你确定结果本身不会超过long long那中间过程最多也就是结果值的若干倍基本不会溢出。所以更稳妥的办法是预先估算C(n, k)如果大于约1e18就直接切换其他方案。公式法还有一个变体是用double算完再转long long我不建议这么干。double的精度只有15到16位有效数字C(100, 50)是1e29级别的数double能表示量级但根本存不准后面的位数全部失真。整数计算就老老实实用整数类型别跟浮点数较劲。3. 方法二递推法适合批量查询3.1 帕斯卡恒等式与杨辉三角公式法每次都要跑循环如果你要查很多组(n, k)组合每次都重新算一遍就很浪费。这时候递推法就派上用场了。递推法的核心是帕斯卡恒等式C(n, k) C(n-1, k-1) C(n-1, k)边界条件C(n, 0) C(n, n) 1。这个恒等式的组合意义很直观从n个元素里选k个可以分两种情况讨论——选中第n个元素那还需要从剩下n-1个里选k-1个或者不选第n个元素那需要从剩下n-1个里选k个。两种情况相加就是总数。如果把这个递推关系画成二维表格每一行对应一个n每一列对应一个k那就是杨辉三角。这个三角有几个特点第一列和主对角线都是1其他位置等于左上角加正上方。这些性质对写代码很有帮助边界处理一目了然。3.2 二维打表和滚动数组优化最直接的实现是开一个二维数组把整个杨辉三角存下来#include iostream using namespace std; const int MAXN 1000; long long C[MAXN 1][MAXN 1]; void init() { for (int i 0; i MAXN; i) { C[i][0] C[i][i] 1; for (int j 1; j i; j) { C[i][j] C[i - 1][j - 1] C[i - 1][j]; } } } int main() { init(); cout C[10][3] endl; // 120 cout C[100][50] endl; // 略大于1e29超出long long演示而已 return 0; }这段代码的时间复杂度是O(MAXN的平方)空间复杂度也是O(MAXN的平方)。MAXN取1000时数组大小约1e6个long long8MB内存完全没问题。但如果你把MAXN开到10000那就是1e8个long long整整800MB普通机器直接崩给你看。空间上有个经典的优化递推第i行时只会用到第i-1行所以不必存完整二维表用一维数组滚动更新就行。关键点是内层循环必须从后往前遍历否则前一个状态会被覆盖const int MAXN 1000; long long C[MAXN 1]; void init_1d(int n, int k) { C[0] 1; for (int i 1; i n; i) { for (int j min(i, k); j 1; j--) { C[j] C[j] C[j - 1]; } } // 结果在C[k] }为什么从后往前遍历因为C[j] C[j] C[j-1]这个式子里的C[j-1]必须是上一轮计算得到的旧值。如果从前往后遍历C[j-1]已经被更新成当前行的新值了结果就不对。这是一个非常经典的动态规划空间优化技巧你在其他一维DP里也会经常遇到养成这个意识很重要。3.3 什么时候用递推、什么时候别用递推法最大的优势是“一次计算多次查询”。初始化完成之后任何C(n, k)都是O(1)时间读表这在竞赛里非常吃香。比如很多概率DP题要反复用到组合数用递推法打表最合适不过。它的劣势也明显一是内存占用会随MAXN平方增长所以MAXN不能太大一般1000到3000是常用范围二是只能处理n小于等于MAXN的情况如果你在跑完初始化后又来了一个超出范围的大n就得扩大数组重新打表。综合来看递推法的黄金场景是“n在几千以内、需要大量查询组合数”。超过这个范围要么用公式法单次计算要么上质因数分解法。4. 方法三质因数分解法不怕大数据4.1 核心思路把组合数变成质因数加减前两种方法在n很大时都很无力因为中间结果动辄几十位甚至上百位数字。质因数分解法提供了另一个角度不直接算大数而是先把组合数分解成质因数的乘积形式最后再统一做乘法。思路是这样的C(n, k) n! / (k! * (n-k)!)只要把分子分母的每个阶乘都质因数分解相同质因子的指数做加减就能得到C(n, k)的质因数分解式。之后把所有质因子按指数的幂次乘起来就是最终结果。那么问题就变成了n!里到底有多少个质因子p这一步有现成公式count n/p n/p^2 n/p^3 ... 直到p^i大于n为止这个公式的原理是n!里p出现的次数等于1到n里所有数字含p的次数的总和。floor(n/p)统计的是至少含一个p的数floor(n/p^2)统计的是至少含两个p的数以此类推。累加起来就是完整计数。4.2 完整代码实现与逐步拆解我直接给出完整实现包括欧拉筛质数、阶乘质因子指数计算、以及高精度乘法输出三部分#include iostream #include vector using namespace std; const int MAXN 1000000; int primes[MAXN]; bool notPrime[MAXN]; int primeCnt 0; // 欧拉筛线性复杂度筛出1到n的所有质数 void sieve(int n) { notPrime[0] notPrime[1] true; for (int i 2; i n; i) { if (!notPrime[i]) { primes[primeCnt] i; } for (int j 0; j primeCnt i * primes[j] n; j) { notPrime[i * primes[j]] true; if (i % primes[j] 0) break; } } } // 计算n!中质因子p的指数 int factorialExp(int n, int p) { int res 0; while (n) { n / p; res n; } return res; } // 高精度乘法vector倒序存储十进制数字乘以一个小整数x void multiplyBig(vectorint num, int x) { int carry 0; for (int i 0; i (int)num.size(); i) { long long cur 1LL * num[i] * x carry; num[i] cur % 10; carry cur / 10; } while (carry) { num.push_back(carry % 10); carry / 10; } } // 组合数质因数分解法返回倒序存储的结果 vectorint C_factor(int n, int k) { if (k n - k) k n - k; if (k 0 || k n) return {0}; sieve(n); // 计算每个质因子在组合数中出现的指数 vectorint exponent(primeCnt, 0); for (int i 0; i primeCnt primes[i] n; i) { exponent[i] factorialExp(n, primes[i]) - factorialExp(k, primes[i]) - factorialExp(n - k, primes[i]); } // 把所有质因子的幂乘起来得到高精度结果 vectorint result(1, 1); for (int i 0; i primeCnt primes[i] n; i) { for (int j 0; j exponent[i]; j) { multiplyBig(result, primes[i]); } } return result; } void printBig(const vectorint num) { if (num.empty() || (num.size() 1 num[0] 0)) { cout 0; return; } for (int i (int)num.size() - 1; i 0; i--) { cout num[i]; } cout endl; } int main() { vectorint res C_factor(100, 50); printBig(res); return 0; }这段代码可以分三块理解。筛质数块用的是欧拉筛每个合数只会被它的最小质因子筛掉一次整体时间复杂度是O(n)比埃氏筛的O(n log log n)略优。对n1e6的场景欧拉筛毫秒级完成不会成为瓶颈。阶乘质因子指数块就是套公式。比如n100, p2时factorialExp(100, 2) 100/2 100/4 100/8 100/16 100/32 100/64 502512631 97。也就是说100!里有97个因子2。这个计算过程只需要除法操作不会产生大数非常轻量。高精度乘法块是整套实现里最“笨”但也最稳的部分。它用vector倒序存储数字原理就是小学学过的竖式乘法——从低位到高位逐位乘以x再逐位处理进位。x本身不超过1e6所以每一位乘上x再加上进位也不超过long long范围不会溢出。最后打印时从vector末尾倒序输出就是正常数字顺序。4.3 高精度输出与扩展取模、大范围场景质因数分解法计算C(100, 50)得到的精确值大约是1.0089e29用long long根本存不下但用上面的代码轻松算出精确结果。这就是它最大的价值不要求结果在标准整数范围内也能精确输出。实际使用时n能开到多大主要瓶颈在最后的高精度乘法。C(100000, 50000)的位数大约有30100位乘法过程中每一位都要反复乘、进位O(位数 × 质因子个数)的复杂度在中高n下会开始变慢。我的实际经验是n在几千以内结果是秒出n在几万时需要等一下n到几十万上百万建议谨慎使用优先考虑是否能用取模解法替代。如果你只需要组合数对某个质数取模的结果比如C(n, k) % mod可以不要高精度乘法直接在最后算幂取模或者换成卢卡斯定理处理n很大的情况。质因数分解法此时依然能用——先算出每个质因子的指数再用快速幂分别计算p^exp % mod最后乘起来。这是它在竞赛里的常见变体。另外一个冷门小妙招如果只关心C(n, k)的奇偶性不需要完整算直接用位运算判断(n k) k成立就是奇数否则是偶数。这是卢卡斯定理的一个推论省时省力写题的时候偶尔能救命。5. 常见问题与排查技巧实录5.1 溢出与精度问题的排查我见过最多的问题是为什么我按公式写n21就开始输出负数原因很简单21!约5.1e19已经超过long long上限9.22e18溢出后变成了负数。所以如果你用了“先算三个阶乘再相除”的写法n21就是第一个崩溃点。即使改成边乘边除的优化写法也只能把安全范围推高到n66左右再往上还得换方案。所以排查溢出问题时先确认你的数据范围是多少再决定采用哪种方法。不要死磕一种方法也别轻易引入double精度问题在组合数计算里比溢出更隐蔽——它不报错但结果悄悄错。还有一个细节很多人会在递推里用int存结果。当n35左右时C(35, 17)已经是4.5e9超出int上限必须用long long。如果打表的结果可能会超过long long建议直接用高精度存储或提前换方案。5.2 递推表内存与初始化问题用递推法打表最怕的是内存超限。二维数组的长度别一上来就拍脑袋定先算一下内存long long占8字节MAXN5000时二维数组就是5000×5000×8200MB。很多在线判题系统的内存限制是256MB你光一个表就占掉大半再加上其他数据就危险了。我的建议是能用滚动数组就用滚动数组把空间降O(n)非要完整打表时先确认MAXN再估算内存。如果对内存不放心可以把long long换成int但前提是确认组合数不会超过2e9。初始化时机也是个小坑。二维打表的init函数要在main最开始调用如果某个查询可能出现在init之前就会读到未初始化的垃圾值。这个错误有时候很难发现因为默认的全局数组初始值是0而C[5][2]未知时也恰好是0测试小数据看不出毛病一到边界就出问题。5.3 选型速查表与实战建议最后整理一份速查表方便你按实际场景快速决策你的需求推荐方法理由只算一次C(n, k)n ≤ 60公式法代码短O(k)计算无需额外内存单次计算但n较大不要取模质因数分解法绕过中间大数输出高精度同一个n多次查询不同k递推法二维表打表后O(1)读结果n较大且内存吃紧只查几次递推法滚动数组空间O(n)但每次结果可能覆盖需注意读取时机只需要C(n, k) % p质因数分解法快速幂适合p不要求是质数的情况n在1e9级别且p为大质数卢卡斯定理不在本文展开需要进一步学习但确实是标准解法组合数计算这事情方法不在多关键是你得知道每种方法的适用范围和局限性。我自己做项目时这三种方法至少会被用到两次一次是快速原型验证阶段的公式法一次是批量数据处理阶段的递推法。只有碰到那种“必须精确输出极大组合数”的需求时我才会把质因数分解法的代码翻出来。最后分享一个小技巧任何计算组合数的代码写完之后一定要顺手验证几个边界值。C(n, 0)1、C(n, n)1、C(n, 1)n还有C(5, 2)10、C(10, 3)120这些经典值都过一遍再跑极端数据比如n66或n67看看会不会溢出。我每次写完都会做这一步它帮我拦下过不少低级错误。