排列组合是经常遇到的问题，本篇文章想跟大家探讨一下，对于给定的，我们该如何去求组合数
。
方法一：递归（动态规划）
基于公式：，很容易就能写出递归解法，当然我们可以用动态规划进行优化，二维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;
}
