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非常小，t非常大，即模数是小素数的高次。这个时候问题被退化到差不多O(k)的复杂度，k很大的情况下会很慢。但是经过测试，平均的情况非常快。
下面给出代码
CombinationNumber.cpp
包含一个比扩展lucas更稳定的版本
（很长，包括了需要用到的所有模块，同余方程组素数表什么的都在，用的时候记得先生成素数表）：
PS:公式5： Wilson定理，当然这东西是什么不重要，因为都会被约掉。
ym
ym
Orz!!!!!!!....
verygood ,i find it at last ! thank you !
公式6能不能再说详细点- -
按我的理解是 从大往小数有k/p段被约掉了 剩下k%p段应该是
(n-k +k%p)*...*(n-k+1)
___________________
(k%p)*...*1
这个与c(k%p,n%p) 同余是怎么推出来的？
@eggeek
公式6其实很好理解，关键是对同余的性质深的理解。对于只包含加减乘除的同余式，首先保证原式确实是整数，并且，所有的数和模数互素。则在过程中对任意元素任意取模结果都等价（当然，模数不能是别的^^）。如果实在无法理解，请把除法看成是乘上逆元（这个过程可逆），并且，乘法情况下，这种等价性我相信你应该很清楚的（也很容易证明）。这个性质自己得好好理解才是，应该可以证明，交换群都有这个性质^^
@eggeek
最后那句说多了，这个其实和交换群并无关系。其实只要证明除法和乘法逆元等价，就无压力了。你的站改可能来自于对它的更直观理解，个人觉得，这种理解可能不存在。因为存在一个更匪夷所思的性质：只要结果是整数，则运算过程中即使交换了除法顺序，导致中间结果原本是不存在的情况（中间结果原本不是整数），结果也会是对的。