卢卡斯(Lucas)定理

前置知识

乘法逆元

定理

$$C^n_m\ (\ mod\ p)\equiv C_{m\ mod\ p}^{n\ mod\ p}*C^{\lfloor\frac{n}{p} \rfloor}_{\lfloor\frac{m}{p} \rfloor}\ (\ mod\ p)$$

代码实现

p 为素数，且 p<=1e8

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef  long double lb;
const int maxn=1e5+7;
ll jc[maxn];
inline ll ksc(ull x,ull y,ll p)
{
	return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
ll fastPow(ll a,ll b,ll p)
{
	ll res=1;
	a%=p;
	while(b)
	{
		if(b&1) res=ksc(res,a,p);
		a=ksc(a,a,p);
		b>>=1;
	}
	return res;
}
inline ll inv(ll a,ll p)
{
	return fastPow(a,p-2,p);
}
ll Lucas(ll n,ll m,ll p)//n为总和，m为需取数，p为模数，且p为质数
{
	if(m>n) return 0;
	if(n==m||m==0) return 1;
	if(n>p||m>p)
		return Lucas(n/p,m/p,p)*Lucas(n%p,m%p,p)%p;
	return jc[n]*inv(jc[m],p)%p*inv(jc[n-m],p)%p;
}
void init(int p)
{
	jc[0]=1;
	for(int i=1; i<=p; ++i) jc[i]=jc[i-1]*i%p;
}
int main()
{
	ll n,m,p;
	cin>>n>>m>>p;
	init(p);
	cout<<Lucas(n,m,p)<<endl;
	return 0;
}

p 为素数，且 p>1e8

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef  long double lb;
const int maxn=1e5+7;
inline ll ksc(ull x,ull y,ll p)
{
	return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
ll fastPow(ll a,ll b,ll p)
{
	ll res=1;
	a%=p;
	while(b)
	{
		if(b&1) res=ksc(res,a,p);
		a=ksc(a,a,p);
		b>>=1;
	}
	return res;
}
inline ll inv(ll a,ll p)
{
	return fastPow(a,p-2,p);
}
ll C(ll n,ll m,ll p)
{
	if(m>n) return 0;
	ll up=1,down=1;//分子分母
	for(int i=n-m+1; i<=n; i++) up=up*i%p;
	for(int i=1; i<=m; ++i) down=down*i%p;
	return up*inv(down,p)%p;
}
ll Lucas(ll n,ll m,ll p)//n为总和，m为需取数，p为模数，且p为质数
{
	if(m>n) return 0;
	if(n==m||m==0) return 1;
	return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main()
{
	ll T,n,m,p;

	cin>>T;
	for(ll i=1; i<=T; ++i)
	{
		cin>>n>>m>>p;
		cout<<Lucas(n+m,m,p)<<endl;
	}
	return 0;
}

n，m较大且p不为素数的时候-拓展卢卡斯定理