【数论】求组合数的四种方法

您所在的位置：网站首页 › 组合数计算法则 › 【数论】求组合数的四种方法

【数论】求组合数的四种方法

#【数论】求组合数的四种方法| 来源: 网络整理| 查看: 265

组合数的常用公式

$1.\; \; \; C_n^m = \frac{A_n^m}{A_m^m}$

$2.\; \; \; C_n^m = \frac{n!}{m!(n - m)!}$

$3.\; \; \; C_{n + 1}^m = C_n^m + C_n^{m - 1}$

零、纯暴力法

根据第一个公式，将 $C_n^m$ 的分子和分母求出，再相除即可。

适用范围：n，m较小的情况下。

时间复杂度： $O(m)$

第一种部分代码如下：

for(int i = n; i >= n - m + 1; i--) ans *= i; for(int i = m; i >= 1; i--) ans /= i;

第二种部分代码如下：

fz = 1, fm = 1; // fz表示分子，fm表示分母 for(int i = n, j = 1; j = 1; } return res; } ll C(ll a, ll b, int p){ // 求组合数C(a, b) if(a < b) return 0; ll fz = 1, fm = 1; // fz表示分子，fm表示分母 for(int i = a, j = 1; j > m; Euler_seive(n); for(int i = 0; i < cnt; i++){ // 求每个质因数出现的次数 int p = primes[i]; sum[i] = get(n, p) - get(m, p) - get(n - m, p); } vector ans; ans.push_back(1); for(int i = 0; i < cnt; i++) // 用高精度乘法将转换后所有剩下的质因数相乘 for(int j = 0; j < sum[i]; j++) ans = mul(ans, primes[i]); for(int i = ans.size() - 1; i >= 0; i--) // 输出答案 cout

【本文地址】

【数论】求组合数的四种方法

【数论】求组合数的四种方法

今日新闻

推荐新闻