luogu P3807 【模板】卢卡斯定理

求 C(n,n+m)%p

C(m,n)%p=C(m%p,n%p)*C(m/p,n/p)

#include<cstdio>

#include<cstring>

#include<iostream>

#define N 4000010

using namespace std;

#define int long long

int jc[N],inv[N],p;

inline int ksm(int x,int y,int mod){

	int ans=1;

	while(y){

		if(y&1)ans=(ans*x)%mod;

		x=(x*x)%mod;

		y>>=1;

	}

	return ans;

}

inline int C(int x,int y){

	if(y>x)return 0;

	return jc[x]*inv[x-y]%p*inv[y]%p;

}

int n,m;

inline void pre(){

	jc[0]=1;for(int i=1;i<p;i++)jc[i]=(jc[i-1]*i)%p;

	inv[p-1]=ksm(jc[p-1],p-2,p);

	for(int i=p-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%p;

}

inline int lucas(int n,int m){

	if(!m)return 1;

	return C(n%p,m%p)*lucas(n/p,m/p)%p;

}

signed main(){

	int T;

	cin>>T;

	while(T--){

		cin>>n>>m>>p;

		n=n+m;

		pre();

		cout<<lucas(n,m)<<endl;

	}

}

巴特西

luogu P3807 【模板】卢卡斯定理

最新文章

热门文章