组合数取模与卢卡斯定理

本文主要是介绍组合数取模与卢卡斯定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD
证明：
设t = MOD / i , k = MOD % i
则有 t * i + k == 0 % MOD
有 -t * i == k % MOD
两边同时除以ik得到：-t * inv[k] == inv[i] % MOD
即 inv[i] == -MOD / i * inv[MOD%i]
即 inv[i] == ( MOD - MOD / i) * inv[MOD%i]
（适用于MOD是质数的情况，能够O(n)时间求出1~n对模MOD的逆）
（转自：http://blog.csdn.net/iamzky/article/details/21246493）

A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]…a[0]，B=b[n]b[n-1]…b[0]。
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…*C(a[0],b[0]) modp同余
即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
eg：以求解n! % p为例，把n分段，每p个一段，每一段求的结果是一样的。但是需要单独处理每一段的末尾p, 2p, …，把p提取出来，会发现剩下的数正好又是(n / p)!，相当于划归成了一个子问题，这样递归求解即可。
这个是单独处理n!的情况，当然C(n,m)就是n!/(m!*(n-m)!)，每一个阶乘都用上面的方法处理的话，就是Lucas定理了，注意这儿的p是素数是有必要的。
Lucas最大的数据处理能力是p在10^5左右
(转自：http://blog.csdn.net/pi9nc/article/details/9615359)

常见取值情况：
（1）1$\leq$m$\leq$n$\leq$1000和1$\leq$p$\leq$${10^9}$

 这个问题比较简单，组合数的计算可以靠杨辉三角，那么由于和的范围小，直接两层循环即可。

（2）1$\leq$m$\leq$n$\leq$${10^18}$和2$\leq$p$\leq$${10^5}$，并且是素数
这个问题有个叫做Lucas的定理，定理描述是，如果：
n=${n_k}{p^k}$+${n_{k-1}}{p^{k-1}}$+${n_{k-2}}{p^{k-2}}$+…+${n_1}p$+${n_0}$
m=${m_k}{p^k}$+${m_{k-1}}{p^{k-1}}$+${m_{k-2}}{p^{k-2}}$+…+${m_1}p$+${m_0}$
那么得到 ${C_n^m}$=${\prod_{i=0}^k }$${C_{n_i}^{m_i}}$(mod p)
这样然后分别求，采用逆元计算即可。（根据费马小定理：(m!(n-m)!)的逆元为 ${(m!(n-m)!)^{p-2}}$ ）
（3）1$\leq$m$\leq$n$\leq$${10^6}$和1$\leq$p$\leq$${10^5}$，并且可能为合数
这样的话先采取暴力分解，然后快速幂即可。
（转自：http://blog.csdn.net/acdreamers/article/details/8037918）

这篇关于组合数取模与卢卡斯定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---