首页 > 笔记 > 关于Lucas定理的证明

关于Lucas定理的证明

更好的阅读体验请移步

引言

和DP证了一下午。。。lucas定理适用于组合数取模,且取模的数为质数。

结论

我们令,则

证明过程

这里用到了一种构造的思想。

先介绍一个二项式定理

据说是牛顿dalao发现的。

还有一个不知道是什么的结论,可以用二项式定理推出

推断过程:

但是对于这个式子只有当的时候,前面的组合数不是的倍数,所以当时,,当时,,所以

我们现在构造一个方程:

则根据我们的推论:

我们把它用二项式定理拆开:

我们再把第一个式子用二项式定理拆一下:

别忘了式(1)式(2)都是的展开式,所以他们的每个项的系数是一样的!

下面是最巧妙的一步,我们来研究一下这两个式子的的系数是什么:

对于式(1),应为,对于式(2),应为,所以得

我们就得到了结论

证毕。

应用

在编程方面,我们可以这样看lucas定理

这就是一个递归式,我们可以每次算出,递归求解,就可以了。伪代码:

 

来一道裸题zoj3557


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×