1.递推方法（杨辉三角）

空间、时间 $O(n ^ 2)$

$C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod$

2.组合数公式（快速幂求逆元）

空间 $O(n)$、时间 $O(n)$

$C_{n}^{m} = \frac{n!}{(n - m)! m!}$

费马小定理 : 假如 $p$ 是质数，且 $gcd(a,p) = 1$, 那么 $a^{p-1} ≡ 1\ (mod\ p)$
所以 $a*a^{p-2} ≡ 1\ (mod\ p)$
得出 : $a^{p-2}$ 就是 $a$ 的乘法逆元
乘法逆元 == $qpow(x, p - 2)$

或者线性求逆元

用 $f[\ ]$ 存储阶乘，$g[\ ]$ 存储阶乘逆元$(mod\ p)$

$C_{n}^{m} = f_n * g_{n - m} * g_m $

3.卢卡斯(Lucas)定理

空间$O(p)$、时间$O(log_p n)$ $(n,m \leq 1e18, p \leq 1e5)$

$C_{n}^{m} = C_{n / p}^{m / p}\ C_{n\ mod\ p}^{m\ mod\ p}(mod\ p)$

用第二种方法预处理 < p 的部分，然后用卢卡斯定理递归拆分为很多$n\ mod\ p$ 与 $m\ mod\ p$求解