求组合数

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

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

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

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];
}

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

组合数一般都比较大，通常题目都要求我们将最终结果对一个质数 取模（ 一般是 ），这种情况下有更快的做法。基于公式：。我们最终要求的是 ，模运算与基本四则运算有些相似，其加、减、乘都满足结合律：
但对于除法却不成立，即 。于是就有了乘法逆元这个概念：对于正整数 和 ，方程 的最小正整数解 就被称为是 模 的逆元，记作 。
那么对于 ，我们如何求这个 呢，两边同时乘以 ，就得到了 ，因此
为防止溢出，可先对每个因子取模，这里为了简化没有写，现在问题的关键就在于如何求逆元了。
对于逆元 的计算，因为 是一个质数，而且一般情况下 与 互质，可以利用费马小定理：

这样就直接得到，用快速幂求解即可，如果你还不懂快速幂，强烈建议去看这篇文章快速幂算法（全网最详细地带你从零开始一步一步优化）

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;
}