求组合数

作者: Plutorres | 来源:发表于2021-04-22 17:44 被阅读0次

算法模板(六)基础数论
求组合数
组合数模板
AcWing 886. 求组合数 II
【计算机数学】组合数知识
【C语言】求组合数
Lucas
Oracle 集合处理sql
redis05集合
python-基础篇03 练习题

排列组合是经常遇到的问题，本篇文章想跟大家探讨一下，对于给定的 $n、m$ ，我们该如何去求组合数 $C^{m}_{n}$ 。

方法一：递归（动态规划）

基于公式： $C^{m}_{n} = C^{m}_{n-1} + C^{m-1}_{n-1}$ ，很容易就能写出递归解法，当然我们可以用动态规划进行优化，二维dp还可以用滚动数组优化成一维dp，这里我直接给出一维dp的写法（跟01背包类似，注意从高位开始更新数组）。复杂度 $O(n^2)$ 。

typedef long long ll;

// 滚动数组dp，求组合数
ll combine(int n, int m) {
    m = min(m, n-m);
    ll c[m+1]; memset(c, 0, sizeof c);
    c[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= 1; j--) {
            c[j] = c[j] + c[j-1];
        }
    }

    return c[m];
}

方法二：乘法逆元+费马小定理+快速幂

组合数一般都比较大，通常题目都要求我们将最终结果对一个质数 $p$ 取模（ $p$ 一般是 $10^9 + 7$ ），这种情况下有更快的做法。基于公式： $C^{m}_{n} = \frac{n!}{m!(n-m)!}$ 。我们最终要求的是 $C^{m}_{n} \% p$ ，模运算与基本四则运算有些相似，其加、减、乘都满足结合律：
$(a + b) \% p = (a \% p + b \% p) \% p$ $(a - b) \% p = (a \% p - b \% p) \% p$ $(a * b) \% p = (a \% p * b \% p) \% p$ 但对于除法却不成立，即 $(a / b) \% p ≠ (a \% p\ / \ b \% p) \% p$ 。于是就有了乘法逆元这个概念：对于正整数 $a$ 和 $p$ ，方程 $(a*x) \% p = 1$ 的最小正整数解 $x_0$ 就被称为是 $a$ 模 $p$ 的逆元，记作 $inv(a, p)$ 。
那么对于 $\frac{a}{b} \%p = m$ ，我们如何求这个 $m$ 呢，两边同时乘以 $(b*inv(b, p)) \% p（值为1）$ ，就得到了 $(a*(inv(b, p))\%p = m$ ，因此
$C^{m}_{n} \% p = n! * inv(m!,p) * inv((n-m)!, p) \% p$ 为防止溢出，可先对每个因子取模，这里为了简化没有写，现在问题的关键就在于如何求逆元了。
对于逆元 $inv(a, p)$ 的计算，因为 $p$ 是一个质数，而且一般情况下 $a$ 与 $p$ 互质，可以利用费马小定理：
$a^{p-1} \% p = 1$
这样就直接得到 $inv(a, p) = a^{p-2}\%p$ ，用快速幂求解即可，如果你还不懂快速幂，强烈建议去看这篇文章快速幂算法（全网最详细地带你从零开始一步一步优化）

typedef long long ll;
const int p = 1e9 + 7;

// 费马小定理快速幂求逆元 b^(p-1) % p = 1，inv(b) = b^(p-2)
// 求 b^n % p
ll quickPow(ll b, ll n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res*b%p;
        n >>= 1;
        b = b*b%p;
    }

    return res;
}

// 乘法逆元求组合数取模
ll combine2(int n, int m) {
    ll frac[n+1]; // 阶乘数组 frac[i] = i! % p;
    frac[0] = 1;
    for(ll i = 1; i <= n; i++)
        frac[i] = frac[i-1] * i % p;

    return frac[n] * quickPow(frac[m], p-2) % p
           * quickPow(frac[n-m], p-2) % p;
}