前往：我自己搭建的博客
题目
洛谷P3807卢卡斯定理
题解
若p是质数，则对于任意整数1<=m<=n:
如果要多次询问组合数的值，就需要预处理一些值。
注意用了Lucas定理后，可能出现C(0,0)的情况，令它为1。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll n,m,p;
ll s1[maxn],s2[maxn]; //s1[]表示阶乘，s2[]表示逆元前缀积
inline ll C(ll n,ll m) {return n<m ? 0 : s1[n]*s2[m]%p*s2[n-m]%p;}
ll lucas(ll n,ll m) {return (n<=p&&m<=p) ? C(n,m) : lucas(n%p,m%p)*lucas(n/p,m/p)%p;}
inline void pre()
{
s1[0]=s2[0]=s2[1]=1; //注意s2[0]=1很重要
for(ll i=1;i<=p;i++) s1[i]=(s1[i-1]*i)%p;
for(ll i=2;i<=p;i++) s2[i]=(p-p/i)%p*s2[p%i]%p;
for(int i=2;i<=p;i++) s2[i]=s2[i-1]*s2[i]%p;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&p); pre();
printf("%lld\n",lucas(n+m,n));
}
return 0;
}
