『算法-ACM 竞赛-数学-数论』组合数（卢卡斯+扩展卢卡斯）模板

ACM 常用模板合集

#include<cstdio>
const int N = 2000 + 5;
const int MOD = (int)1e9 + 7;
int comb[N][N];//comb[n][m]就是C(n,m)
void init(){
    for(int i = 0; i < N; i ++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= MOD;
        }
    }
}
int main(){
    init();
}

Lucas

#include<iostream>
using namespace std;
typedef long long LL;
const LL N=1e5+2;
LL a[N];
void init(LL p)
{
	a[1]=1;
	for(int i=2;i<=p;++i)a[i]=a[i-1]*i%p;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
LL ksm(LL x,LL n,LL mod)
{
	LL ans=1;
	while(n){
		if(n&1)ans=ans*x%mod;
		n>>=1;
		x=x*x%mod;
	}
	return ans;
}
LL C(LL n,LL m,LL p)
{
	if(n==m||m==0)return 1;
	if(n<m)return 0;
	if(m*2>n)m=n-m;						  /*C(n,m)=c(n,n-m)*/
	return a[n]*ksm(a[m]*a[n-m],p-2,p)%p; /*求(a[m]*a[n-m])在(mod p)意义下的乘法逆元*/
										  /*拓展欧几里得与费马小定理均可*/
	/*LL x,y;
	exgcd(a[m]*a[n-m],p,x,y);
	return (a[n]*x%p+p)%p;*/
}
LL lucas(LL n,LL m,LL p)
{
	if(!m)return 1;
	return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main()
{
	ios::sync_with_stdio(false);
	LL T,n,m,p;
	cin>>T;
	while(T--){
		cin>>n>>m>>p;
		init(p);
		cout<<lucas(n+m,m,p)<<endl;
	}
	return 0;
}

ExLucas

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+9;
LL A[N],M[N];
LL ksm(LL x,LL n,LL mod)
{
	LL ans=1;
	while(n){
		if(n&1)ans=ans*x%mod;
		n>>=1,x=x*x%mod;
	}
	return ans;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}
LL inv(LL a,LL p)
{
	LL x,y;
	exgcd(a,p,x,y);
	return (x+p)%p?x:x+p;
}
LL get(LL n,LL pi,LL p)									/*求(与pi互素后的n!)%M[i]*/
{
	if(!n)return 1;
	LL ans=1;
	if(n/p){											/*判断有无循环节 */
		for(LL i=2;i<=p;++i)if(i%pi)ans=ans*i%p;
		ans=ksm(ans,n/p,p);
	}
	for(LL i=2;i<=n%p;++i)if(i%pi)ans=ans*i%p;			/*循环节剩余部分*/
	return ans*get(n/pi,pi,p)%p;
}
LL exlucas(LL n,LL m,LL pi,LL p)						/*求A[i]*/
{
	LL nn=get(n,pi,p);									/*求(与pi互素后的n)%M[i]*/
	LL mm=get(m,pi,p);									/*求(m!与pi互素后的m!)%M[i]*/
	LL nm=get(n-m,pi,p);								/*求(与pi互素后的(n-m)!)%M[i]*/
	LL k=0;												/*含质因数pi的数量*/
	for(LL i=n;i;i/=pi)k+=i/pi;
	for(LL i=m;i;i/=pi)k-=i/pi;
	for(LL i=n-m;i;i/=pi)k-=i/pi;
	return nn*inv(mm,p)*inv(nm,p)*ksm(pi,k,p)%p;
}
LL crt(LL len,LL Lcm)
{
	LL ans=0;
	for(LL i=1;i<=len;++i){
		LL Mi=Lcm/M[i];
		ans=((ans+A[i]*inv(Mi,M[i])*Mi)%Lcm+Lcm)%Lcm;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	LL n,m,P,num;
	while(cin>>n>>m>>P){
		if(n<m){
			cout<<0<<endl;
			continue;
		}
		num=0;
		memset(A,0,sizeof(A));
		memset(M,0,sizeof(M));
		for(LL x=P,i=2;i<=P;++i)
			if(x%i==0){
				M[++num]=1;
				while(x%i==0){
					M[num]*=i;
					x/=i;
				}
				A[num]=exlucas(n,m,i,M[num])%P;
			}
		cout<<crt(num,P)<<endl;
	}
	return 0;
}