洛谷P3807 【模板】卢卡斯定理_组合数学模板

Code:

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000+2;
LL mod;
int MAXN;
struct comb{
	LL fac[maxn];
	LL quick_pow(LL base,LL k)
	{
		LL ans=1;
		while(k)
		{
			if(k&1)ans=(ans*base)%mod;
		    k/=2;
			base=(base*base)%mod;
	    }
	    return ans;
    }
    void init()
    {
    	fac[1]=fac[0]=1;
    	for(int i=2;i<MAXN;++i)fac[i]=(fac[i-1]*i)%mod;
    }
    LL get_inv(LL num){return quick_pow(num,mod-2);}
    LL C(LL n,LL m)
    {
    	if(m==0)return 1;
    	if(n<m)return 0;
    	return (fac[n]*get_inv(fac[n-m]*fac[m]))%mod;
    }
    LL Lucas(LL n,LL m)
    {
    	if(m==0)return 1;
    	//if(n>=mod&&m>=mod)return C(n,m);
    	return (Lucas(n/mod,m/mod)*C(n%mod,m%mod))%mod;
    }
}op;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		LL a,b;
		scanf("%lld %lld %lld",&a,&b,&mod);
		MAXN=a+b+3;
		op.init();
		printf("%lld
",op.Lucas(a+b,a));
	}
	return 0;
}