标签：组合 mathrm int ll fac comb inv mod

递推法

时间复杂度：O(n*m)

const int N=2010;
const int mod=1e9+7;
ll C[N][N];
void init(){
  for(int i=0; i<N; i++) C[i][0] = 1;
  for(int i=1; i<N; i++)
  	for(int j=1; j<=i; j++)
      		C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;  
}

公式法

时间复杂度：O(n)

[公式]

\[\begin{gathered} \mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!} =\frac{n!}{m!(n-m)!},\quad n,m\in\mathbb{N}^*,\text{并且}m\leq n \\ \mathrm{C}_n^0=\mathrm{C}_n^n =1 \end{gathered} \]

const int N = 2000010;
const int mod = 1e9 + 7;

ll inv_fac[N], fac[N];
ll qmi(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv_fac[N - 1] = qmi(fac[N - 1], mod - 2);
    for (int i = N - 1; i >= 1; i--) {
        inv_fac[i - 1] = inv_fac[i] * i % mod;
    }
}
ll comb(int n, int k) {
    return fac[n] * inv_fac[k] % mod * inv_fac[n - k] % mod;
}

标签：组合,mathrm,int,ll,fac,comb,inv,mod
From： https://www.cnblogs.com/taotao123456/p/17883566.html