lucas板子求调

/*卢卡斯定理*/
//背景:求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;
const int N=1e5+10;
int f[N],g[N];
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;
}
void init(int p)
{
	f[0]=g[0]=1;
	for(int i=1;i<=p;i++)
	{
		f[i]=f[i-1]*i%p;
		g[i]=g[i-1]*ksm(i,p-2,p)%p;
	}
}
ll getC(ll n,ll m,ll p)
{
	if(n<m)return 0;
	return f[n]*g[m]*g[n-m]%p;
}
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;
	init(p);
	cin>>n>>m>>p;
	cout<<lucas(n,m,p);
}