O(N^2) 求组合数 $C^m_n$

根据$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$
初始化$C_i^0 = 1$，然后开始递推即可

1
2
3
4
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

$O(N)$求组合数

根据$C_n^m = \frac{n!}{m! \times (n - m)!}$
O(n)预处理出阶乘以及阶乘的逆元，每次求 $C_n^m$ 均为O(1)

1
2
3
4
5
6
7
8
9
10
11
fact[0] = infact[0] = 1;
// 快速幂求逆元
infact[N - 1] = qmi(infact[N - 1], mod - 2);
for (int i = 1; i < N; i ++ ) {
    fact[i] = fact[i - 1] * i % mod;
}

//可以类比于除法去考虑
for (int i = N - 2; i >= 1; i--) {
    infact[i] = infact[i + 1] * (i + 1) % mod;
}

卢卡斯定理求组合数

卢卡斯定理：若p是质数，则对于任意整数 $1 \leq m \leq n$，有：
$C_n^m = C_{n \bmod p}^{m \bmod p} \times C_{n / p}^{m / p} \pmod p $
当题目中发现，模数是质数，并且 $p \leq n$ 时，可使用卢卡斯定理。