C++算法实战：组合计数核心方法与工程应用详解

1. 项目概述：为什么组合计数是C++算法入门的“必修课”？

如果你刚开始接触C++编程，尤其是准备踏入算法竞赛或者想夯实编程基础，那么“组合计数”这个概念，你大概率绕不过去。它听起来有点数学，有点抽象，但相信我，它远比你想象的要贴近实际。简单来说，组合计数就是解决“有多少种可能”的问题。比如，从5个不同的玩具里选2个送给朋友，有多少种送法？这就是一个典型的组合问题。在C++的世界里，无论是解决经典的“爬楼梯”问题（每次走1或2阶，到第n阶有多少种走法？），还是设计一个抽奖程序计算中奖概率，甚至是编写一个自动生成测试用例的工具，组合计数的思想都无处不在。

我刚开始学算法时，也觉得排列组合是数学课的内容，和编程关系不大。直到在一次在线编程挑战中，我卡在了一道看似简单的题目上：计算从一堆字符中生成所有不重复的密码组合的数量。当时我试图用暴力循环去枚举，结果不仅代码冗长，而且当数据量稍大时程序就直接超时了。后来才知道，这本质上就是一个组合数计算问题，用公式C(n, m)几行代码就能秒解。那次经历让我深刻意识到，组合计数不是可选的数学知识，而是编写高效、优雅C++程序的底层工具之一。它帮你把“数数”这个动作，从直觉性的枚举，升级为基于数学模型的精确计算，这是算法思维的核心飞跃。

对于初学者，掌握基础组合计数能帮你解决两大痛点：一是避免写出时间复杂度爆炸的暴力代码；二是能让你更清晰地定义问题。很多复杂的动态规划、图论问题，其状态转移的本质就是组合计数。因此，这份指南的目标不是把你变成数学家，而是作为一个有经验的开发者，带你绕过我当年踩过的坑，直击核心，用C++这把利器，把组合计数的概念变成你代码中实实在在、高效运行的部分。我们会从最根本的公式和概念入手，然后聚焦于如何在C++中实现它们，并处理那些大数、溢出等实际编程中一定会遇到的“拦路虎”。

2. 核心概念拆解：排列、组合与二项式定理

在动手写代码之前，我们必须把几个核心概念及其关系彻底厘清。这部分是地基，地基不稳，后面所有巧妙的算法都是空中楼阁。

2.1 排列 (Permutation)：顺序至关重要

排列关心的是“顺序”。从n个不同元素中，取出m（m ≤ n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列。所有不同排列的个数，就是排列数，记作 P(n, m) 或 A(n, m)。

它的计算公式是：P(n, m) = n! / (n-m)!其中n!表示n的阶乘，即n! = n × (n-1) × ... × 2 × 1。

生活化类比：想象你要给一场比赛的前三名颁奖（冠军、亚军、季军），有8位选手。那么颁奖顺序（谁得金、谁得银、谁得铜）就是至关重要的。这就是一个排列问题：P(8, 3) = 8 * 7 * 6 = 336 种可能的颁奖结果。

在C++中的思考：计算排列数最直接的方法就是利用阶乘。但这里马上会遇到第一个坑：阶乘增长极快！13! 就已经超过32位整型（int）的表示范围了。所以，直接计算大数的阶乘再相除，在编程中通常是行不通的，极易溢出。我们稍后会介绍更安全的计算方法。

2.2 组合 (Combination)：只关心“有没有”

组合不关心顺序，只关心“有没有被选出来”。从n个不同元素中，取出m（m ≤ n）个元素并成一组，叫做从n个元素中取出m个元素的一个组合。所有不同组合的个数，就是组合数，记作 C(n, m)，也常写作n choose m，即C(n, m)。

它的计算公式由排列数衍生而来：C(n, m) = P(n, m) / m! = n! / [m! * (n-m)!]

为什么除以 m!？因为从n个元素中任选m个，这m个元素本身有 m! 种排列方式。组合不计较这m个内部的顺序，所以要把这些重复的排列数除掉。

生活化类比：还是那8位选手，但现在不是颁奖，而是选拔3人组成一个团队代表学校参赛。只要人选确定，团队就确定了，谁是一号队员、谁是二号队员并不重要。这就是一个组合问题：C(8, 3) = (876) / (321) = 56 种可能的团队组成方式。你会发现，组合数（56）远小于排列数（336），正是因为我们除去了内部顺序带来的重复。

2.3 二项式定理 (Binomial Theorem)：组合数的“集大成者”

二项式定理揭示了组合数与代数展开之间的深刻联系。公式如下：(x + y)^n = C(n,0)*x^n*y^0 + C(n,1)*x^(n-1)*y^1 + ... + C(n,k)*x^(n-k)*y^k + ... + C(n,n)*x^0*y^n

这个定理的强大之处在于：

1. 计算工具：它提供了一种计算 (1+1)^n 即 2^n 的方法，而 2^n 正好等于所有组合数之和：C(n,0)+C(n,1)+...+C(n,n)。这在分析算法复杂度（比如子集枚举）时非常有用。
2. 理解对称性：从定理可以直接看出组合数的对称性：C(n, m) = C(n, n-m)。因为等式右边 x^(n-m)y^m 项的系数是 C(n, m)，而它等于 x^my^(n-m) 项的系数 C(n, n-m)。
3. 递推关系：它隐含了帕斯卡法则（Pascal‘s Rule）：C(n, m) = C(n-1, m-1) + C(n-1, m)。这个递推关系是动态规划计算组合数的基石。

实操心得：初学者常常死记硬背组合数公式。我的建议是，深刻理解“排列是带顺序的选择，组合是不带顺序的选择”，以及“组合数等于排列数除以所选元素的内部排列数”。理解了这个，公式自然就记住了。二项式定理则像一座桥梁，让你看到离散的组合数与连续的代数之间的美妙联系，在解决一些特定类型的求和问题时（比如证明某些恒等式），它能提供降维打击般的思路。

3. C++实现组合计数的四大核心方法

理论清晰了，现在进入实战环节。在C++中计算组合数，根据数据范围和对效率、精度的要求，我们有几种不同的武器。选择哪种，是区分新手和有经验者的关键。

3.1 方法一：直接计算与阶乘的陷阱

这是最直观的方法，直接套用公式C(n, m) = n! / (m! * (n-m)!)。

#include <iostream> using namespace std; // 计算阶乘函数 long long factorial(int n) { long long result = 1; for (int i = 2; i <= n; ++i) { result *= i; } return result; } // 直接计算组合数 long long combinationDirect(int n, int m) { if (m < 0 || m > n) return 0; // 非法输入处理 return factorial(n) / (factorial(m) * factorial(n - m)); } int main() { int n = 10, m = 3; cout << "C(" << n << ", " << m << ") = " << combinationDirect(n, m) << endl; // 输出：C(10, 3) = 120 return 0; }

致命缺陷与注意事项：

• 溢出！溢出！溢出！：这是该方法最大的问题。long long类型通常能安全存储的最大阶乘是20!（约2.4e18）。21!就会溢出。这意味着该方法仅适用于 n <= 20 的极小范围。在算法竞赛中，n=1000甚至100000都是家常便饭，此方法完全无效。
• 效率低下：计算了三次阶乘，存在大量重复计算。
• 整数除法：在C++中，两个整数相除结果仍是整数，但这里因为数学上保证结果是整数，所以没问题。但如果先计算n! / m!再除以(n-m)!，中间结果可能更大，更容易溢出。

提示：除非题目明确 n 非常小（<=20），否则永远不要在正式代码中使用这种基于完整阶乘的计算方法。它只是一个用于理解概念的教学示例。

3.2 方法二：递推法与动态规划（DP）思想

利用帕斯卡法则C(n, m) = C(n-1, m-1) + C(n-1, m)，我们可以用动态规划（一个二维数组）来预先计算一定范围内的所有组合数。这是最常用、最实用的方法之一。

#include <iostream> #include <vector> using namespace std; const int MAX_N = 1000; // 根据问题规模设定 const long long MOD = 1e9 + 7; // 常见的模数，用于处理大数 vector<vector<long long>> comb(MAX_N + 1, vector<long long>(MAX_N + 1, 0)); void computeCombinations() { // 初始化：C(n, 0) = C(n, n) = 1 for (int i = 0; i <= MAX_N; ++i) { comb[i][0] = comb[i][i] = 1; } // 递推计算 for (int i = 2; i <= MAX_N; ++i) { for (int j = 1; j < i; ++j) { // 核心递推公式，取模防止溢出 comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } } long long combinationDP(int n, int m) { if (m < 0 || m > n) return 0; return comb[n][m]; } int main() { computeCombinations(); // 预处理 int n = 100, m = 50; cout << "C(" << n << ", " << m << ") mod " << MOD << " = " << combinationDP(n, m) << endl; return 0; }

为什么这种方法强大？

1. 预处理，O(1)查询：一旦computeCombinations函数执行完毕，之后任何C(n, m)（n <= MAX_N）的查询都是常数时间。这在需要多次查询组合数的问题中效率极高。
2. 天然支持取模运算：算法竞赛中，结果往往需要对一个大质数（如1e9+7）取模，以避免溢出。递推过程中的加法运算可以很方便地融入取模操作。
3. 直观体现了动态规划思想：这是学习DP的一个完美入门案例。状态comb[i][j]表示C(i, j)，状态转移方程就是帕斯卡法则。

实操心得与避坑指南：

• 空间复杂度：二维数组的大小是 O(n^2)。当 MAX_N=5000时，内存消耗约为 500050008字节 ≈ 200MB，可能超出限制。此时需要考虑优化，比如只使用两行数组的滚动数组法，但查询会变麻烦。
• 初始化：务必正确初始化C(i, 0)和C(i, i)为1。这是递推的起点。
• 模运算：如果题目要求取模，每一步加法后都要立即取模，否则中间结果可能溢出long long。

3.3 方法三：乘法逆元与费马小定理（处理大质数模数）

当我们需要计算C(n, m) % MOD，且 MOD 是一个质数（如 1e9+7）时，可以利用数论中的“逆元”来直接套用阶乘公式，同时避免溢出。这是处理超大n（如1e5, 1e6）的利器。

核心思路：

1. 预处理出1!到n!的阶乘数组fact[i]，以及每个阶乘在模 MOD 下的逆元数组invFact[i]。
2. 组合数C(n, m) % MOD = fact[n] * invFact[m] % MOD * invFact[n-m] % MOD。
3. 关键是如何求逆元？当 MOD 是质数时，根据费马小定理，a关于模 MOD 的乘法逆元inv(a) = a^(MOD-2) % MOD。我们可以用快速幂算法高效计算。

#include <iostream> #include <vector> using namespace std; const int MAX_N = 100000; // 可以处理更大的n const long long MOD = 1e9 + 7; vector<long long> fact(MAX_N + 1); vector<long long> invFact(MAX_N + 1); // 快速幂算法：计算 (base^exp) % MOD long long fastPow(long long base, long long exp) { long long result = 1; base %= MOD; while (exp > 0) { if (exp & 1) { // 如果exp是奇数 result = (result * base) % MOD; } base = (base * base) % MOD; exp >>= 1; // exp /= 2 } return result; } void precomputeFactorials() { fact[0] = 1; for (int i = 1; i <= MAX_N; ++i) { fact[i] = fact[i-1] * i % MOD; } // 计算 MAX_N! 的逆元，然后倒推所有阶乘的逆元 invFact[MAX_N] = fastPow(fact[MAX_N], MOD - 2); for (int i = MAX_N - 1; i >= 0; --i) { invFact[i] = invFact[i+1] * (i+1) % MOD; } } long long combinationMod(int n, int m) { if (m < 0 || m > n) return 0; // 核心公式：C(n,m) = n! / (m!*(n-m)!) = n! * inv(m!) * inv((n-m)!) return fact[n] * invFact[m] % MOD * invFact[n-m] % MOD; } int main() { precomputeFactorials(); int n = 100000, m = 50000; // 传统方法无法处理的大数 cout << "C(" << n << ", " << m << ") mod " << MOD << " = " << combinationMod(n, m) << endl; return 0; }

为什么这是“降维打击”？

• 时间复杂度：预处理 O(n + log MOD)，查询 O(1)。对于单次查询，甚至可以不预处理，直接计算三个阶乘和两个逆元，复杂度 O(n + log MOD)，也比递推法计算单个值快（递推法计算单个值需O(n^2)？不，那需要整个表。计算单个值用此法最优）。
• 空间复杂度：O(n)，两个一维数组，比递推法的二维数组小得多。
• 处理范围：n 可以达到 1e6 甚至更大（取决于内存），只要 MOD 是质数。

注意：这个方法的前提是MOD 必须是质数，且 MOD > n（通常都满足，如1e9+7远大于1e6）。如果 MOD 不是质数，则需要使用扩展欧几里得算法求逆元，复杂许多。

3.4 方法四：卢卡斯定理（处理n, m巨大但模数p较小的情况）

当 n 和 m 非常大（比如10^18），但模数 p 是一个不大的质数时，递推和逆元法都无法处理（因为无法预处理到n）。这时就需要卢卡斯定理 (Lucas Theorem)。

定理内容：C(n, m) % p = C(n%p, m%p) * C(n/p, m/p) % p这是一个递归定义，不断将 n 和 m 对 p 取模和除以 p，直到商为0。

// 假设已实现小范围的组合数计算函数 combinationSmall(n, m)，例如用递推或逆元法，n,m < p long long lucasTheorem(long long n, long long m, int p) { if (m == 0) return 1; // 递归应用卢卡斯定理 return (combinationSmall(n % p, m % p, p) * lucasTheorem(n / p, m / p, p)) % p; }

应用场景：典型的就是某些数学竞赛或特定题目中，要求计算C(10^18, 10^17) % 9973这样的值。直接算不可能，但用卢卡斯定理，我们只需要能计算n, m < 9973的组合数即可，瞬间将问题规模降到可处理范围。

实操心得：卢卡斯定理是“化大为小”的典范。在实现时，combinationSmall函数必须高效且能处理模 p 运算。通常 p 较小，直接用递推法预处理一个 p*p 的二维数组（因为 n%p, m%p 都小于p）是最快的。记住，它只适用于模数 p 是质数的情况。

4. 典型应用场景与实战代码剖析

掌握了计算方法，我们来看看组合计数在C++编程中具体能解决哪些问题。光说不练假把式，这里我结合几个经典场景，给出代码实现和思路分析。

4.1 场景一：生成所有子集（组合枚举）

问题：给定一个数组nums，生成它的所有可能的子集（包括空集）。这是组合问题的直接体现，每个元素都有“选”或“不选”两种状态，总共2^n个子集。

方法1：位运算掩码法（最常用）

#include <iostream> #include <vector> using namespace std; void generateSubsets(const vector<int>& nums) { int n = nums.size(); int total = 1 << n; // 2^n for (int mask = 0; mask < total; ++mask) { vector<int> subset; for (int i = 0; i < n; ++i) { // 检查第i位是否为1 if (mask & (1 << i)) { subset.push_back(nums[i]); } } // 此时 subset 就是一个子集，可以处理或输出 cout << "{ "; for (int num : subset) cout << num << " "; cout << "}" << endl; } } int main() { vector<int> nums = {1, 2, 3}; generateSubsets(nums); return 0; }

原理：用一个整数mask的二进制位来表示选择状态。第 i 位为1表示选择nums[i]，为0表示不选。从0遍历到2^n - 1，就遍历了所有可能的状态。子集总数2^n = C(n,0) + C(n,1) + ... + C(n,n)，完美对应组合数求和。

方法2：递归回溯法（更通用）

void backtrack(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) { result.push_back(path); // 当前路径（子集）加入结果 for (int i = start; i < nums.size(); ++i) { path.push_back(nums[i]); // 选择 nums[i] backtrack(nums, i + 1, path, result); // 递归处理下一个位置 path.pop_back(); // 撤销选择，回溯 } }

原理：递归树上的每一个节点都对应一个子集。这种方法更容易扩展到“限制子集大小（如固定长度m）”、“有重复元素需要去重”等变体问题。

4.2 场景二：计算路径问题（网格行走）

经典问题：在一个 m x n 的网格中，从左上角(0,0)走到右下角(m-1, n-1)，每次只能向右或向下移动一步，总共有多少条不同的路径？

分析：从起点到终点，总共需要向右走 (n-1) 步，向下走 (m-1) 步。无论路径如何曲折，总步数是固定的(m-1)+(n-1)。一条路径就等价于在这总步数中，选择何时向下走（或何时向右走）。因此，路径总数就是组合数：C( (m-1)+(n-1), (m-1) )或C( (m-1)+(n-1), (n-1) )。

#include <iostream> using namespace std; // 使用递推法计算组合数 long long uniquePaths(int m, int n) { // 总步数 steps = m + n - 2， 向下走的步数 down = m - 1 int steps = m + n - 2; int down = m - 1; // 计算 C(steps, down) // 使用 long long 并注意防止中间结果溢出，这里用递推思想直接计算 long long ans = 1; // 计算 C(steps, down) = steps! / (down! * (steps-down)!) // 优化计算：计算 [steps, steps-down+1] 的乘积，再除以 down! // 等价于计算 C(steps, down) = C(steps, steps-down)，取小的那个计算 if (down > steps - down) down = steps - down; // 利用对称性，减少计算量 for (int i = 1; i <= down; ++i) { ans = ans * (steps - down + i) / i; // 关键：边乘边除，避免溢出 } return ans; } int main() { int m = 3, n = 7; cout << "Unique paths in a " << m << "x" << n << " grid: " << uniquePaths(m, n) << endl; // 输出：28 return 0; }

关键技巧：ans = ans * (steps - down + i) / i;这行代码是精髓。它通过交替进行乘法和除法，保证了在计算过程中ans始终是整数（因为组合数一定是整数），并且最大限度地避免了中间结果溢出long long的范围。这是一种计算单个组合数非常高效且安全的方法，尤其适用于不需要取模的场景。

4.3 场景三：容斥原理解决计数问题

有些计数问题，直接计算“符合条件”的情况很难，但计算“不符合条件”的情况相对容易。这时可以用“总情况数”减去“不符合条件的情况数”。但如果“不符合条件”的情况有重叠，就需要容斥原理。

经典例题：从1到1000中，有多少个数能被2、3或5整除？

分析：

• 设A：能被2整除的数的集合。
• 设B：能被3整除的集合。
• 设C：能被5整除的集合。 我们要求 |A ∪ B ∪ C|。 根据容斥原理： |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

其中：

• |A| = floor(1000/2) = 500
• |A∩B| = 能被2和3整除，即能被6整除， floor(1000/6) = 166
• |A∩B∩C| = 能被2,3,5整除，即能被30整除， floor(1000/30) = 33 ... 以此类推。

C++实现：

#include <iostream> #include <vector> using namespace std; long long countDivisible(int N, vector<int>& primes) { int k = primes.size(); long long total = 0; // 遍历所有非空子集 (用位运算) for (int mask = 1; mask < (1 << k); ++mask) { long long lcm = 1; // 当前子集对应数的最小公倍数 int bits = 0; // 子集中元素的个数 for (int i = 0; i < k; ++i) { if (mask & (1 << i)) { bits++; // 简单计算lcm，假设两两互质，则lcm为乘积。非互质需用gcd计算。 lcm *= primes[i]; // 如果lcm已经大于N，则对答案贡献为0，可提前跳出 if (lcm > N) { lcm = 0; break; } } } if (lcm == 0) continue; // lcm太大，跳过 long long count = N / lcm; // 1..N中能被lcm整除的数的个数 // 根据子集元素个数的奇偶性，决定加还是减（容斥原理） if (bits % 2 == 1) { total += count; } else { total -= count; } } return total; } int main() { int N = 1000; vector<int> primes = {2, 3, 5}; cout << "Numbers divisible by 2, 3, or 5 up to " << N << ": " << countDivisible(N, primes) << endl; // 验证：|A|=500, |B|=333, |C|=200, |A∩B|=166, |A∩C|=100, |B∩C|=66, |A∩B∩C|=33 // 500+333+200-166-100-66+33 = 734 return 0; }

核心思想：容斥原理的本质是“先加后减，多减再加”。在代码中，我们枚举了质数集合的所有非空子集。每个子集对应一个“最小公倍数”lcm。如果子集大小为奇数，就加上能被lcm整除的数的个数；大小为偶数，就减去。这完美实现了容斥公式。这种“枚举子集+容斥”的模式，是解决复杂计数问题的强大工具。

5. 常见陷阱、调试技巧与性能优化

即使理解了算法，在实际编码中依然会踩坑。下面是我在多年实践中总结的一些“血泪教训”和优化技巧。

5.1 数值溢出：最大的“隐形杀手”

这是组合计数问题中最常见、最隐蔽的错误。即使最终结果在数据类型范围内，中间计算过程也可能溢出。

案例：计算C(100, 50)。结果约是1e29，远超long long范围。但如果你用边乘边除的方法ans = ans * (n-i+1) / i，由于除法是整数除法且能整除，中间过程ans可能不会太大，但如果你先计算分子product = (n-i+1) * ...，再除以i!，分子在除以i!之前就可能已经溢出了。

防御策略：

1. 预估结果范围：在计算前，用斯特林公式或对数大致估算结果。如果远超数据类型范围，必须使用高精度库或取模运算。
2. 优先使用递推法或逆元法（取模）：在算法竞赛和大多数应用中，结果取模是标准要求。这两种方法在运算过程中就进行取模，天然防溢出。
3. 使用边乘边除技巧：对于不取模的精确计算，确保乘法后紧跟除法，且除法能整除。顺序很重要，有时需要调整乘除顺序以保证整除性。
4. 使用高精度库：对于需要精确大整数结果的情况（如某些数学题），C++没有原生支持，需要使用boost::multiprecision::cpp_int或手动实现大整数类。

5.2 边界条件与特殊输入处理

永远不要相信用户的输入，或者题目保证的输入范围。健壮的程序必须处理边界。

• m > n或m < 0：根据组合数定义，C(n, m)在这种情况下应为0。你的函数必须检查并返回0。
• n == 0或m == 0：C(0, 0)通常定义为1。C(n, 0) = C(n, n) = 1。
• n或m为负数：组合数通常定义在非负整数上，遇到负数应视为非法输入，返回0或抛出异常。
• MOD可能为1：在取模运算中，如果MOD = 1，那么所有结果都是0。但通常MOD是大质数，不过检查一下无害。

long long safeCombination(int n, int m, long long MOD) { if (n < 0 || m < 0 || m > n) return 0; if (m == 0 || m == n) return 1 % MOD; // ... 正常计算过程 }

5.3 性能优化实战

当n很大或查询次数极多时，性能成为关键。

1. 预处理 vs 即时计算：

   • 多次查询：绝对要预处理！无论是递推表还是阶乘逆元表，O(n^2)或O(n)的预处理开销换来O(1)的查询，是稳赚的。
   • 单次查询：如果n不大，用边乘边除法。如果n很大且需要取模，用基于费马小定理的逆元法即时计算（O(n + log MOD)），这比构建整个递推表快。

2. 利用对称性：C(n, m) = C(n, n-m)。计算时，令m = min(m, n-m)，可以节省近一半的计算量。这在边乘边除法和某些递推中很有效。

3. 记忆化搜索：如果递推关系复杂，或者计算是递归的（如某些包含组合数的递归式），可以使用记忆化搜索（Memoization）避免重复计算。用unordered_map或数组存储已计算的结果。

4. 模运算优化：

   • 加减乘运算后立即取模。
   • 避免使用%运算符进行不必要的取模。如果知道数值远小于MOD，可以跳过。
   • 对于固定模数的乘法，如果编译器支持，可以使用__int128中间类型来避免溢出，然后再取模。

5.4 调试与验证技巧

1. 小数据暴力验证：用最直接的阶乘法（n很小，如n<=10）计算出正确结果，作为“暴力标准答案”，来验证你优化后的算法（递推、逆元等）是否正确。
2. 利用已知恒等式：
   • 求和验证：C(n,0) + C(n,1) + ... + C(n,n) = 2^n。计算你预处理好的组合数一行，求和看是否等于1 << n（对2^n取模后）。
   • 帕斯卡法则验证：随机取几个n, m，检查C(n,m)是否等于C(n-1,m-1)+C(n-1,m)。
3. 输出中间结果：在计算逆元时，打印出前几个fact[i]和invFact[i]，检查fact[i] * invFact[i] % MOD是否等于1。
4. 使用静态分析工具：对于潜在的整数溢出，一些编译器的静态分析选项（如GCC的-ftrapv）或在代码中使用-fsanitize=undefined可以在运行时检测到溢出错误。

组合计数是C++算法学习中一个承上启下的关键模块。它连接了基础的数学思维和高效的编程实现。我个人的体会是，不要畏惧其中的数学公式，而是要把它们看作解决问题的蓝图。从理解“为什么这样算”出发，到掌握“在C++里怎么安全高效地算”，最后到“遇到实际问题怎么想到用这个算”，每一步都离不开动手实践和踩坑总结。当你能够熟练地根据数据范围（n, m的大小，是否取模）和查询模式（单次还是多次）快速选择最合适的计算方法时，你就真正把这把利器收入囊中了。最后分享一个我常用的决策树：n <= 20 用阶乘（仅教学）；需要多次查询且n <= 5000，用递推DP；n很大(1e5)且MOD为质数，用逆元法；n巨大(1e18)但p小，用卢卡斯定理；需要精确值且范围大，用高精度库。