Lucas定理,是用来快速求解一个组合数对于一个数(保证这一个数是质数)的模。
那么,我们先来看Lucas定理的求解式:
(binom{n}{m}%p)((p)是质数)
这样的一个式子,在(n,mleq 10^9)的时候很容易炸掉,那么我们就要对它利用(p)进行化简求值 。
那么,我们可以将(n,m)用另一种形式处理(可以考虑成将(n,m)用(p)进制表示)
(n=n_kcdot p^k + n_{k-1}cdot p^{k-1} + cdots + n_1cdot p + n_0)
(m=m_kcdot p^k + m_{k-1}cdot p^{k-1} + cdots + m_1cdot p + m_0)
那么,(binom{n}{m}equivbinom{n_k}{m_k}binom{n_{k-1}}{m_{k-1}}cdotsbinom{n_0}{m_0} (mod p))
是不是看起来很累啊,我们换一种方法(binom{n}{m}equivprod_{i=0}^{k}binom{n_i}{m_i} (mod p))
(p是质数就不写了哈,反正所有的p都是质数)
我们接下来证明:(不喜欢看这一段的同学直接看代码啦)
令(n=acdot p+b,m=ccdot p+d)
(therefore a=left lfloor frac{n}{p} right rfloor,b=left lfloor frac{m}{p} right rfloor)
引理1:$(1+x)^p equiv 1+x^p pmod{p} $
证明:
$(1+x)^p equiv 1+x pmod{p} $
(x^p equiv x pmod{p})
(1+x^p equiv 1+x pmod{p})
(therefore (1+x)^p equiv 1+x^p pmod{p})
证毕
((1+x)^n=(1+x)^{left lfloor frac{n}{p} right rfloor cdot p}cdot (1+x)^b equiv (1+x^p)^{left lfloor frac{n}{p} right rfloor}cdot (1+x)^b)
此处引入二项式定理:((1+x)^n=sum_{i=0}^{n}binom{n}{i}cdot x^i)
(therefore (1+x^p)^{left lfloor frac{n}{p} right rfloor}cdot (1+x)^b=sum_{i=0}^{a}binom{a}{i}x^{pcdot i}cdot sum_{j=0}^{b}binom{b}{j}x^j)
((1+x)^n=sum_{m=0}^{n}binom{n}{m}x^m)
(sum_{i=0}^{a}binom{a}{i}x^{pcdot i}cdot sum_{j=0}^{b}binom{b}{j}x^j=sum_{pi+j leq m且j<p}binom{a}{i}binom{b}{j}x^{pi+j})
(because pi+j=m)
(therefore binom{a}{i}binom{b}{j}=binom{n}{m})
接下来迭代证明即可。
那么代码实现也十分简单。
【模板】卢卡斯定理
板子题,直接上板子:
#include <cstdio>
#define Maxn 100000
int n,m,p;
int inv[Maxn+5];
int a[Maxn+5];
int ksm(int x,int y){
int ans=1;
while(y){
if(y&1){
ans=(int)((long long)ans*x%p);
}
y>>=1;
x=(int)((long long)x*x%p);
}
return ans;
}//求逆元
int C(int x,int y){
if(y>x){
return 0;
}
return (int)(1ll*a[x]%p*ksm(a[y],p-2)%p*ksm(a[x-y],p-2)%p);
}//求组合数
int lucas(int x,int y){
if(y==0){
return 1;
}
return (int)(lucas(x/p,y/p)*1ll*C(x%p,y%p)%p);
}//lucas,用递归实现极为简单
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&p);
a[0]=1;
for(int i=1;i<=p;i++){
a[i]=(int)(a[i-1]*1ll*i%p);
}//预处理
printf("%dn",lucas(n+m,n));
}
return 0;
}