大组合数取模的Lucas定理

一般情况下，我们计算大组合数取模问题是用递推公式进行计算的：

其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加，在实践中不适用。当这时候就需要Lucas定理进行快速运算:

其中：

证明方法也很简单，主要用到如下等式：

应用这个公式，可以的到如下递归式

这里的Lucas(n,m,p)就是C_n^m\ mod\ p，递归终点就是当n=0的时候。时间复杂度是O(log_p(n)*p).