一般情况下，我们计算大组合数取模问题是用递推公式进行计算的：
$$
C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p
$$
其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加$O(mn)$，在实践中不适用。当这时候就需要Lucas定理进行快速运算:
$$
C_n^m=\prod_{i=0}^{k}C_{n_i}^{m_i}\ mod\ p
$$
其中：
$$
m=m_kp^k+m_{k-1}p^{k-1}+…+m_1p+m_0
$$
$$
n=n_kp^k+n_{k-1}p^{k-1}+…+n_1p+n_0
$$
证明方法也很简单，主要用到如下等式：
$$
C_p^j\equiv 0\ mod\ p\ ( 1 \leq j \leq p-1 )
$$
$$
(1+x)^{p}\equiv 1+x^p \ mod\ p
$$
应用这个公式，可以的到如下递归式
这里的$Lucas(n,m,p)$就是$C_n^m\ mod\ p$，递归终点就是当n=0的时候。时间复杂度是$O(log_p(n)*p)$.