Lucas定理

[原文]2017-02-14

[update]2017-03-28

Lucas定理

计算组合数取模，适用于n很大p较小的时候，可以将计算简化到小于p

$ \binom{n}{m} \mod p , p is prime$

$ n= n_k * p ^ k + n_{k-1} * p^{k-1}+ ... + n_2 * p^2 + n_1 * p + n_0 $

$ m=m_k * p ^ k +m_{k-1} * p^{k-1}+ ... +m_2 * p^2 +m_1 * p+m_0 $

$ \binom{n}{m} = \prod\limits_{i=0}^k \binom{n_i}{m_i} $

证明见参考资料 ~~我不会告诉你我没看的~~

实现：这个形式很像多项式啊变量为p，n和m迭代/=p然后算C(n%p,m%p)就行了

逆元也可以线性预处理

复杂度，如果忽略阶乘的话，应该是$O(\log_pN)$吧

inv[1]=1; fac[0]=facInv[0]=1;for(int i=1; i<=n; i++) {    if(i!=1) inv[i] = (P-P/i)*inv[P%i]%P;    fac[i] = fac[i-1]*i%P;    facInv[i] = facInv[i-1]*inv[i]%P;}

ll lucas(int n, int m) {    if(n

扩展Lucas定理

$P is not prime $

$P$进行质因子分解，然后对于每个质因子$p_i^{e_i}$都得到一个同余方程

$x\equiv a_i\pmod {p_i^{e_i}}\ $

用中国剩余定理合并就行了

但是$ \binom{n}{m}\mod p_i^{e_i} $怎么求？

只要计算阶乘就行了，我们分成三部分：

比如：

$ n!=1∗2∗3∗4∗5∗6∗7∗8∗9∗10∗11∗12∗13∗14∗15∗16∗17∗18∗19 $

$ =(1∗2∗4∗5∗7∗8∗10∗11∗13∗14∗16∗17∗19)∗3^6∗(1∗2∗3∗4∗5∗6) $

假设当前质因子为$p$，$p_i^{e_i}=pr$

第一部分

$p$的倍数，有$\frac{n}{p}$个，提出$p$后形成了新的阶乘，递归解决

第二部分

提出的$p$ 因为不满足互质没法求逆元，所以放在最后计算$n!$中$p$出现次数然后分数线上-下就行了

计算方法：$x=\lfloor{n\over p}\rfloor+\lfloor{n\over p^2}\rfloor+\lfloor{n\over p^3}\rfloor+...$

证明？这不就是这整个求阶乘算法过程产生的数量吗？

第三部分

不是$p$的倍数的部分；可以按$pr$分块，一共$\frac{n}{pr}$块，结果都是相同的；最后一块暴力计算即可

复杂度：计算阶乘模$p^a$时复杂度$O(p^a)$

ll Pow(ll a,ll b,ll P){    ll ans=1;    for(;b;b>>=1,a=a*a%P)        if(b&1) ans=ans*a%P;    return ans;}void exgcd(ll a,ll b,ll &d,ll &x,ll &y){    if(b==0) d=a,x=1,y=0;    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;}ll Inv(ll a,ll n){    ll d,x,y;    exgcd(a,n,d,x,y);    return d==1?(x+n)%n:-1;}ll Fac(ll n,ll p,ll pr){    if(n==0) return 1;    ll re=1;    for(ll i=2;i<=pr;i++) if(i%p) re=re*i%pr;    re=Pow(re,n/pr,pr);    ll r=n%pr;    for(int i=2;i<=r;i++) if(i%p) re=re*i%pr;    return re*Fac(n/p,p,pr)%pr;}ll C(ll n,ll m,ll p,ll pr){    if(n