扩展lucas定理

前置知识：

• lucas定理
• 中国剩余定理

介绍

当正整数$n,m$很大，且质数$p$较小的时候，要求$C_n^m$对$p$取模后的值，可以用lucas定理。

但如果$p$不是质数，那该怎么办呢？如果$m$较小，则可以用扩展lucas定理。

第一步：中国剩余定理

设$p=p_1^{r_1}{p}_2^{r_2}\cdots p_k^{r_k}$，其中$p_i$为质数。我们可以先求出$C_n^m\%p_1^{r_1},C_n^m\%p_2^{r_2},\dots ,C_n^m\%p_k^{r_k}$的值$a_1,a_2,\dots ,a_k$。

我们把$C_n^m$看作未知数$x$，可以得到以下方程组：

$$\{\begin{array}{c}x\equiv a_1(\mathrm{mod}{p}_1^{r_1})\\ x\equiv a_2(\mathrm{mod}{p}_2^{r_2})\\ x\equiv a_3(\mathrm{mod}{p}_3^{r_3})\\ ......\\ x\equiv a_n(\mathrm{mod}{p}_k^{r_k})\end{array}$$

利用中国剩余定理，我们可以求出$x$，它是以$p$为周期出现的无穷多个解。而在$[0,p)$这个周期的解，就是$C_n^m\%p$后的值。

那么$a_1,a_2\dots ,a_k$怎么求呢？

第二步：组合数模质数的幂

由第一步可得

$$a=C_n^m\mathrm{mod}{p}^r$$

因为$C_n^m=\frac{n!}{m!(n-m)!}$，我们若要求$m!$和$(n-m)!$关于$p^r$的逆元，则要把其中所有的质因子$p$提出来，再乘回去即可。

$$C_n^m=\frac{n!}{m!(n-m)!}=\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\times \frac{(n-m)!}{p^z}}\times p^{x-y-z}$$

其中$x,y,z$分别是$n!,m!,(n-m)!$中质因子$p$的次数。此时$\frac{m!}{p^y}\times \frac{(n-m)!}{p^z}$与$p^r$互质，可以直接求逆元。因为$C_n^m$为整数，所以$x-y-z\ge 0$，$p^{x-y-z}$可以用快速幂来求。

第三步：阶乘除去质因子后模质数幂

接下来的问题就是计算以下式子

$$\frac{n!}{p^t}\mathrm{mod}{p}^k$$

我们呢先考虑如如何计算$n!\mathrm{mod}{p}^k$。举个例子：$n=22,p=3,k=2$

$22!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12\times 13\times 14\times 15\times 16\times 17\times 18\times 19\times 20\times 21\times 22$

把其中$3$的倍数提出来，得到

$22!=(3\times 6\times 9\times 12\times 15\times 18\times 21)\times (1\times 2\times 4\times 5\times 7\times 8\times 10\times 11\times 13\times 14\times 16\times 17\times 19\times 20\times 22)$

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

其中$3^7$即为$p^k$，就是需要被提出的部分。

对于$7!$，即为$\lfloor \frac{n}{p}\rfloor !$，可以递归来求。

对于后面的部分，我们发现

$1\times 2\times 4\times 5\times 7\times 8\equiv 10\times 11\times 13\times 14\times 16\times 17(\mathrm{mod}{p}^k)$

我们发现$1\times 2\times 4\times 5\times 7\times 8$在整个式子中会出现$\lfloor \frac{n}{p^k}\rfloor$次，因此，我们可以先计算在$p^k$以内的部分，然后再求其$\lfloor \frac{n}{p^k}\rfloor$次幂。不要忘了乘上最后多出的一部分。

$1\times 2\times 4\times 5\times 7\times 8\times 10\times 11\times 13\times 14\times 16\times 17\times 19\times 20\times 22\equiv (1\times 2\times 4\times 5\times 7\times 8{)}^3\times 19\times 20\times 22(\mathrm{mod}{p}^k)$

也就是说，对于以下式子

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

$3^7$是要提出的，不用计算。第二部分可以递归计算。第三部分可以$O(p^k)$得出。

总结

扩展lucas定理与lucas定理在实现上并没有太大关联，只是解决的问题比较类似。扩展lucas定理的时间复杂度大概在$O(p+{\log }^{2}n)$。当然，这是最坏的时间复杂度，一般的时间复杂度远远低于此。如果$p$的质因子比较多且都比较小，则时间复杂度会降低很多。

例题

P4720 【模板】扩展卢卡斯定理

code

#include<bits/stdc++.h>
using namespace std;
int tot=0;
long long mod,x,y,ans=0,a[105],r[105];
long long mi(long long t,long long v){if(v==0) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void exgcd(long long c,long long d){if(d==0){x=1;y=0;return;}exgcd(d,c%d);long long t=x;x=y;y=t-c/d*y;
}
long long gt(long long v,long long p,long long q){if(!v) return 1;long long re=1;for(int i=1;i<=q;i++){if(i%p) re=re*i%q;}re=mi(re,v/q)%q;for(int i=1;i<=v%q;i++){if(i%p) re=re*i%q;}return re*gt(v/p,p,q)%q;
}//第三步
long long C(long long v1,long long v2,long long p,long long q){if(v1<v2) return 0;long long f1=gt(v1,p,q),f2=gt(v2,p,q),f3=gt(v1-v2,p,q),vt=0;for(long long i=p;i<=v1;i*=p) vt+=v1/i;for(long long i=p;i<=v2;i*=p) vt-=v2/i;for(long long i=p;i<=v1-v2;i*=p) vt-=(v1-v2)/i;return mi(p,vt)%q*f1%q*(mi(f2,q-q/p-1)%q)%q*(mi(f3,q-q/p-1)%q)%q;
}//第二步
int main()
{long long n,m,v;scanf("%lld%lld%lld",&n,&m,&mod);v=mod;for(int i=2;i*i<=v;i++){if(v%i==0){r[++tot]=1;while(v%i==0){r[tot]*=i;v/=i;}a[tot]=C(n,m,i,r[tot]);}}if(v>1){r[++tot]=v;a[tot]=C(n,m,v,v);}v=mod;for(int i=1;i<=tot;i++){exgcd(v/r[i],r[i]);x=(x%r[i]+r[i])%r[i];ans=(ans+v/r[i]*a[i]*x%v)%v;}//第一步printf("%lld",ans);return 0;
}