卢卡斯定理适用于求解组合数取模，而且模数为质数且不大的情况。
具体地，卢卡斯定理可以这样表示
$$C_n^m\mod p=C_{n/p}^{m/p}*C_{n\mod p}^{m\mod p}\mod p$$
我们首先预处理出一个阶乘数组，一个mod p的逆元数组，当数值较小时，我们可以直接使用组合数的计算公式$C_n^m=\frac{n!}{m!(n-m)!}$来计算
当数据较大时，我们采用迭代的思路，根据卢卡斯定理将数据缩小，这样，我们就能在O(logpn)的时间内解决问题
原文：https://www.cnblogs.com/shl-blog/p/11235935.html