一般情况下,我们计算大组合数取模问题是用递推公式进行计算的:
其中p相对较小的素数。但是当n和m过大时,计算的耗费就急剧增加,在实践中不适用。当这时候就需要Lucas定理进行快速运算:
其中:
证明方法也很简单,主要用到如下等式:
应用这个公式,可以的到如下递归式
这里的Lucas(n,m,p)就是C_n^m\ mod\ p,递归终点就是当n=0的时候。时间复杂度是O(log_p(n)*p).
本文分享自 作者个人站点/博客 前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!