大组合数取模的Lucas定理

mythsman

发布于 2022-11-14 14:25:12

7830

发布于 2022-11-14 14:25:12

文章被收录于专栏：mythsman的个人博客

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

C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p

其中p相对较小的素数。但是当n和m过大时，计算的耗费就急剧增加，在实践中不适用。当这时候就需要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).

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度