简述
当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 Lucas 定理。
Lucas
Lucas 定理内容如下：
对于质数 \(p\)，有
\[\binom{n}{m} \equiv \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\cdot\binom{n\mod p}{m\mod p}\mod p
\]
\]
上式中\(n\mod p\)和\(m\mod p\)一定小于\(p\)，可以直接求解，\(\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\)继续用 Lucas 定理求解。边界条件：当 \(m=0\) 的时候，返回 \(1\)
复杂度为 \(O(f(p) + g(n)\log n)\)，其中 \(f(n)\) 为预处理组合数的复杂度，\(g(n)\) 为单次求组合数的复杂度。
il int Lucas(int n,int m,int p){
if(!m) return 1;
return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
il int rd(){
ri int x=0,f=1;ri char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x*f;
}
cs int N=1e5+5;
int t,n,m,P,A[N];
il int qpow(int a,int b,int p){
ri int ans=1;
while(b) {
if(b&1) ans=(1ll*ans*a)%p;
a=(1ll*a*a)%p,b>>=1;
}
return ans;
}
il int inv(int a,int p){
return qpow(a,p-2,p);
}
il int C(int n,int m,int p){ // 直接算组合数
if(m>n) return 0;
return 1ll*A[n]*inv(A[m],p)%p*inv(A[n-m],p)%p;
}
il int Lucas(int n,int m,int p){
if(!m) return 1;
return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main(){
t=rd();
while(t--){
n=rd(),m=rd(),P=rd(),A[1]=A[0]=1; // 预处理阶乘
for(ri int i=2;i<P;++i) A[i]=1ll*A[i-1]*i%P;
printf("%d\n",Lucas(n+m,n,P));
}
return 0;
}
exLucas
对于 \(p\) 不是素数的情况，就需要用到 exLucas 定理
AC·code
#include<bits/stdc++.h>
#define il inline int
#define vl inline void
#define cs const
#define ri register
#define int long long
using namespace std;
vl exgcd(int a,int b,int &x,int &y){
(b==0)?(x=1,y=0):(exgcd(b,a%b,y,x),y-=(a/b)*x);
}
il inv(int a,int p){
int x,y;exgcd(a,p,x,y);
return (x%p+p)%p;
}
il qpow(int a,int b,int p){
int as=1;
while(b){
if(b&1) as=(as*a)%p;
a=(a*a)%p,b>>=1;
}
return as;
}
il getf(int n,int p,int pk){
if(!n) return 1;
int as=1;
for(ri int i=2;i<pk;++i){
if(i%p) as=(as*i)%pk;
}
as=qpow(as,n/pk,pk);
for(ri int i=1+pk*(n/pk);i<=n;++i){
if(i%p) as=(i%pk*as)%pk;
}
return as*getf(n/p,p,pk)%pk;
}
il getg(int n,int p){
return (n<p)?0:(getg(n/p,p)+n/p);
}
il getc(int n,int m,int p,int pk){
int fz=getf(n,p,pk),fm1=getf(m,p,pk),fm2=getf(n-m,p,pk);
int qp=qpow(p,getg(n,p)-getg(m,p)-getg(n-m,p),pk);
return qp*fz%pk*inv(fm1,pk)%pk*inv(fm2,pk)%pk;
}
il exlucas(int n,int m,int p){
int res=p,as=0,pk;
for(ri int i=2;i*i<p;++i){
if(res%i==0){
pk=1;
while(res%i==0){
res/=i,pk*=i;
}
as=(as+getc(n,m,i,pk)*inv(p/pk,pk)%p*(p/pk)%p)%p;
}
}
if(res>1){
as=(as+getc(n,m,res,res)*inv(p/res,res)%p*(p/res)%p)%p;
}
return as;
}
signed main(){
int n,m,p;
cin>>n>>m>>p;
cout<<exlucas(n,m,p);
return 0;
}
原文链接: https://www.cnblogs.com/windymoon/p/17072847.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314663
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
