如何计算组合数C(n, m)？

74.Acwing基础课第888题-简单-求组合数Ⅳ 题目描述 \(输入a，b，求 C^b_a的值\)。 输入格式 \(共一行，包含两个整数 a 和 b\)。 输出格式 \(共一行，输出 C^b_a的值\)。 数据范围 \(1≤b≤a≤5000\) 输入样例： 5 3 输出样例： 10 代码： // 包含基础输入输出、算法、向量容器头文件（vector用于存储高精度数） #include <iostream> #include <algorithm> #include <vector> using namespace std; // 常量定义：N=5010，支持计算C(a,b)中a≤5000的组合数 const int N = 5010; // 全局变量： // primes[]：存储1~a范围内的所有质数 // cnt：质数的个数 // sum[]：存储每个质数在组合数中的指数（C(a,b) = ∏(p^sum[p])） // st[]：筛法标记数组（true表示非质数） int primes[N], cnt; int sum[N]; bool st[N]; // 线性筛（欧拉筛）函数：筛选出1~n范围内的所有质数，时间复杂度O(n) // 优势：每个数仅被其最小质因子筛一次，效率高于普通筛法 void get_primes(int n) { // 遍历2~n的所有数 for (int i = 2; i <= n; i ++ ) { // 若未被标记，说明是质数，加入primes数组 if (!st[i]) primes[cnt ++ ] = i; // 用当前质数筛除合数 for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; // 标记primes[j]*i为非质数 // 若i能被primes[j]整除，说明primes[j]是i的最小质因子，退出循环（避免重复筛） if (i % primes[j] == 0) break; } } } // 计算n!中质因子p的指数（公式：n/p + n/p² + n/p³ + ... 直到p^k > n） int get(int n, int p) { int res = 0; // 存储指数总和 while (n) { res += n / p; // 累加n/p（p的倍数个数） n /= p; // 计算更高次幂的倍数个数（p², p³...） } return res; } // 高精度乘法函数：将高精度数a（逆序存储）与低精度数b相乘，返回结果 // 例如：a=[1,2]（表示21），b=2 → 结果=[2,4]（表示42） vector<int> mul(vector<int> a, int b) { vector<int> c; // 存储乘积结果（逆序） int t = 0; // 存储进位 // 遍历高精度数的每一位 for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; // 当前位乘积 + 上一位的进位 c.push_back(t % 10); // 存储当前位的结果（个位） t /= 10; // 更新进位（十位及以上） } // 处理剩余进位（如t=123，需依次存储3、2、1） while (t) { c.push_back(t % 10); t /= 10; } return c; } int main() { int a, b; // a：总数；b：选取数（计算C(a,b)） cin >> a >> b; // 步骤1：筛选出1~a范围内的所有质数 get_primes(a); // 步骤2：计算每个质数在C(a,b)中的指数 // 组合数公式：C(a,b) = a!/(b!*(a-b)!) → 质因子p的指数 = get(a,p) - get(b,p) - get(a-b,p) for (int i = 0; i < cnt; i ++ ) { int p = primes[i]; // 当前质数 sum[i] = get(a, p) - get(a - b, p) - get(b, p); } // 步骤3：高精度乘法计算最终结果（初始为1） vector<int> res; res.push_back(1); // 初始值1（逆序存储：[1]表示1） // 遍历每个质数，按指数乘到结果中 for (int i = 0; i < cnt; i ++ ) for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]); // 步骤4：输出结果（逆序存储，需从后往前遍历） for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]); puts(""); // 换行 return 0; }