Lucas定理推广(组合数取模)
比赛的时候,意外想到了个方法来处理组合数取模。一推,发现就是Lucas定理,并且,在模数是素数乘方的情况作了些推广。使得lucas能够处理模任意数的组合数取模。
Lucas定理
首先给出Lucas定理的递归描述
简要证明思路:
考虑连续的p个整数(p是素数),把能整除p的那个数除去,然后取模,再乘起来模p其实是-1(*)。注意,因为和p互素的原因,这东西是可约的。
再考虑这个组合公式
上下都有k项,你能取的长度为p的连续整数有k/p段(从后往前取),每一段去掉那个能被p整除的数,然后,上下因为有相同的段数,所以就被约掉了(明白为什么在这种情况下是可约的么?)。
为什么能被p整除的数要被单独的拉出来呢?因为,和模数有公因子的数加入取模运算会导致不可逆。所以这些能被p整除的数需要被提取出来单独处理。
于是,有了后面部分的C(n/p, k/p),其实就是每个被提取出来的数再提取了一个因子p(因为上下提取出来的数一样多,所以,这些p自然就被约掉了)。然后,你幸运的发现,他是个组合数,于是问题被递归。最后,我们还有个前缀没有被处理。但是,因为模数是p,所以有下面公式
把这写合并在一起,就有了Lucas定理的递归表述(公式1)
推广的Lucas
那么要怎么处理模数是素数p的乘方的情形呢?其实是一样的,只不过,有些东西就不再退化了,比如公式6。我们可以用同样的方式,先把因子p全部提取出来单独处理,于是得到如下的公式,来处理p的乘方。
其中
式2的前缀(F除以F)就是上面的公式6不能退化的情况。为什么?因为其中可能含有因子p。因子p加入会导致乘法取模的不可逆。
需要注意的是,前缀很可能不是整数,在写代码的时候这个地方很容易犯错!所以要先进入子问题(可以用一个栈搞定)。
一般的组合数取模
有了这些,我们能干什么呢?其实,Lucas及其扩展只是把原来的组合数取模问题分割成了更小规模的问题(有lg(k)/lg(p)个)。
考虑一个一般的问题,模数m任意。
策略:
我们把m先素数分解,然后用Lucas及其扩展分割。然后对每个小问题解决合并。合并可以用CRT进行(同余方程组,中国剩余定理)。于是,如果简单的组合数取模能在O(k)的时间完成,我们就得到一个时间复杂度的算法(其中p是m的素因子,t是该素因子的个数),然后我们需要用lg级别的时间,完成每一个的合并,空间取决于素数表的大小(当然,可以没有,没有的话,就是lg级别的空间了)
可能的退化:如果p非常小,t非常大,即模数是小素数的高次。这个时候问题被退化到差不多O(k)的复杂度,k很大的情况下会很慢。但是经过测试,平均的情况非常快。
下面给出代码
CombinationNumber.cpp
包含一个比扩展lucas更稳定的版本
(很长,包括了需要用到的所有模块,同余方程组素数表什么的都在,用的时候记得先生成素数表):
PS:公式5: Wilson定理,当然这东西是什么不重要,因为都会被约掉。
相关推荐
ACM基础模板(宏定义、快读快写、快速幂、gcd、组合数与Lucas定理)(csdn)————程序
讲述了lucas定理如何求C(n,m)%p^k
排列组合及其推论例题内含有lucas定理
数论
说明:1. 数较小且mod较大时求组合数使用逆元,数较大且mod较小时求组合数用lucas2. 该模版只可以求对于正数的组合数,如果出现负数的情况则返回0使用方
对 Lucas Kanade算法的Pyramidal Implementation
Lucas Kanade 算法资料,包含中英文资料,有几个资料
lucas kanade光流算法的MATLAB实现,感兴趣的可以看看
1.领域:matlab,Lucas-Kanade和Horn-Schunck算法 2.内容:对视频目标进行光流提取,对比Lucas-Kanade和Horn-Schunck+matlab操作视频 3.用处:用于Lucas-Kanade和Horn-Schunck算法编程学习 4.指向人群:本硕博等...
Lucas2
Lucas_Kanade实现的光流算法 基于金字塔模型
基于kanade lucas的跟踪外文文献
光流运动中经典的Lucas_Kanade的matlab算法,适合视频中的目标跟踪运用
大家如果自己有时间进“欧洲土壤光谱数据“官网https://esdac.jrc.ec.europa.eu/content/lucas-2009-topsoil-data#tabs-0-description=1申请下载也行。在官网还可以了解到这个项目的其他情况。 excel你们一看就知道...
开源项目-lucas-clemente-quic-go.zip,quic-go: A QUIC server implementation in pure go
C#,卢卡斯数(Lucas Number)的算法与源代码 卢卡斯数(Lucas Number)是一个以数学家爱德华·卢卡斯(Edward Lucas)命名的整数序列。爱德华·卢卡斯既研究了这个数列,也研究了有密切关系的斐波那契数(两个数列...
lucas-kanade的光流算法原文(1981) 对相关研究具有参考价值。
lucas kanade matlab code can be easily understand
1.版本:matlab2019a,不会运行可私信 2.领域:基础教程 3.内容:Matlab实现Lucas-Kanade 光流金字塔方法 4.适合人群:本科,硕士等教研学习使用