Lucas板子,p过大也没问题

/*卢卡斯定理*/
//背景:求C(n,m)%p,p是质数
//公式:结论1 -> C(p,x)%p=0;
//     结论2 -> [(1+x)^p]%p=1+x^p
//     结论3 -> 卢卡斯：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
//注意:这里p是质数,如果不是质数,移步扩展卢卡斯

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll a,ll b,ll p)
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1)ans*=base,ans%=p;
		base*=base,base%=p;b>>=1;
	}
	return ans;
}
ll getC(ll a, ll b,ll p)   
{
	ll ans = 1;
	for (ll i = 1, j = a; i <= b; i ++, j -- )
	{
		ans = ans * j % p;
		ans = ans * ksm(i, p - 2,p) % p;
	}
	return ans;
}
ll lucas(ll n,ll m,ll p)
{
	if(m==0)return 1;
	return lucas(n/p,m/p,p)*getC(n%p,m%p,p)%p;
}
void solve()
{
	ll n,m,p;
	cin>>n>>m>>p;
	cout<<lucas(n,m,p);
}