Lucas定理

关于卢卡斯定理

卢卡斯定理用于求组合数取模,当 n m 过大时,效率十分高效。
大家在网上的博客上一般可以看见卢卡斯定理表述为

C(n,\ m)\ \equiv\ C(n/p,\ m/p)\ *\ C(n\%p,\ m\%p)\ \%\ p


还有一种方便理解的表示。
Lucas
其中
l
L

 

平时做题

平时做题一般使用第一种方法迭代。将比较大的 n m 变为次大 C(n/p,\ m/p) 的乘一个较小的 C(n\%p,\ m\%p) 。较小的 C(n\%p,\ m\%p) 用求逆元的方法求出来,较大的 C(n/p,\ m/p) 依旧用卢卡斯定理去求。注意预处理阶乘。

 

例题

一道Lucas定理的模板题,HDU3037
题目是一题组合数学题,用插缝法可算出答案为 C(n+m,\ m)\ \%\ p
这道题预处理一下阶乘,用递归法求逆元,或者可以用费马小定理求逆元。
代码中Init()函数为预处理阶乘。Inv(n)为求阶乘。 Lucas(n,m,p)为卢卡斯求解的函数,用了迭代的方法。
下面是题目代码:

 

其他

其实当 p 过大时,Lucas定理的效率并不是太高,主要是空间占用太大。时间复杂度大约为 O(log_{p}n log^{2} p)

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注