一、 直接公式求

组合数的求法 - 图1

二、基于杨辉三角的递推

组合数的求法 - 图2

三、基于逆元的求法

需要进行取模的时候，我们可以使用逆元法加速运算。

  1. //逆元法快速求组合数
  2. #define LL long long
  3. const LL mod = 1e9 + 7;
  4. LL fact[N << 1], inv[N << 1];
  5. //快速幂
  6. LL quickpow(LL a, LL b) {
  7.     LL res = 1;
  8.     while (b) {
  9.         if (b & 1) res = res * a % mod;
  10.         b >>= 1;
  11.         a = a * a % mod;
  12.     }
  13.     return res;
  14. }
  15. //处理n!的逆元
  16. void init(int n) {
  17.     fact[0] = 1;
  18.     for (int i = 1; i <= n; ++i)
  19.         fact[i] = fact[i - 1] * i % mod;
  20.     inv[n] = quickpow(fact[n], mod - 2);
  21.     for (int i = n - 1; i >= 0; --i)
  22.         inv[i] = inv[i + 1] * (i + 1) % mod;
  23. }
  24. LL C(LL n, LL m) {
  25.     if (m > n) return 0;
  26.     return fact[n] * inv[m] % mod * inv[n - m] % mod;
  27. }