用于求$\left( {\begin{array}{*{20}{c}}{n + m}\\m\end{array}} \right)\bmod p$, $p$为质数.

当然也要结合快速幂，不过这里是利用快速幂求逆元的啦~

代码分享

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
//Lucas定理
//结合快速幂使用
typedef long long ll;
int n,m,p,T;
ll qpow(ll x,ll m){
	if(m==0) return 1;
	ll tmp=qpow(x,m>>1);
	tmp=(tmp*tmp)%p;
	if(m%2==1) tmp=(tmp*x)%p;
	return tmp;
} 
ll getc(ll n,ll m){
	if(m>n) return 0;
	if(m>n-m) m=n-m;
	ll s1=1,s2=1;
	for(int i=0;i<m;i++){
		s1=s1*(n-i)%p;
		s2=s2*(i+1)%p;
	}
	return s1*qpow(s2,p-2)%p;
}
ll lucas(ll n,ll m){
	if(m==0) return 1;
	return getc(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&p);
		printf("%d\n",lucas(n+m,m)); 
	}
	return 0;
	}
</pre>