[关闭]
@ArrowLLL 2017-04-06T10:55:42.000000Z 字数 1227 阅读 2561

卢卡斯(Lucas)定理

数学 组合数学 算法


主页地址 :月光森林


引入

之前有写过一篇博客是求组合数(取模)的两种方法。那篇文章里介绍的方法其实也还有局限性,Pascal打表由于内存的限制一般只用于求取1000以内的组合数,而使用逆元套公式的方法其实也只适用于求取的组合数 中,n 和 m均不大于要求的模数 p 。这样就导致了一个很尴尬的问题——如果要求取的组合数超过了模数p,这个时候有要怎么办呢。本人之前由于水平限制并没有了解到这个问题,前几天打玲珑杯#round 4的时候被这个问题困扰了,经队友提醒才知道有Lucas定理这种东西。这里就另写一篇文章,其实是作为之前的“组合数取模的两种方法”的一个拓展篇。将这个问题一次性终结到底。

定义、证明与方法

卢卡斯(Lucas)定理
为素数, ,并且


这里 都是整数,. 则有

这里还要声明一点,本篇博客的参考书籍为冯志刚版《初等数论》第37页,下面给出原书的证明:Lucas定理证明

这个定理的意义就在于把 或者 或者两者均大于 的组合数 转换为求解小于 的整数 的组合数 的乘积。

而对于 可以通过秦九韶算法:


逆向得到,即

显然,秦九韶的逆向算法页同样适用于求解 .

使用解析

实际求解 时,只要 当中有一个仍然大于 ,就要继续使用逆向的秦九韶算法。但实际编写代码的过程,只需要递归即可:

  1. LL Lucas(LL a, LL b)
  2. {
  3. if(a < mod && b < mod)
  4. return C(a, b);
  5. return
  6. C(a % mod, b % mod) * Lucas(a / mod, b / mod);
  7. }

其中C(a, b)的函数在之前的文章求组合数(取模)的两种方法叙述过了,这里就不继续赘述了。

现在,通过pascal打表的方法在 的时间里求得小范围的组合数,用逆元的方法可以求取模数范围内的组合数,在加上Lucas定理,就可以求取任意范围内的组合数了。

在实际运用的过程中,可以根据实际判断哪种方法最适合, 的是一个主导因素,同事,算法的简单性也是一个主导因素。毕竟,越简单的东西越不容易出错。杀鸡用牛刀不是不可以,但是你想过鸡的感受么。。。

以上です~

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注