P3807 【模板】卢卡斯定理

传送门

卢卡斯定理$(Lucas)$：用来求解组合数取模问题：$C(n,m)\%p$

这里直接用百度的定义和推导： (我觉得讲的很清晰了)

推导过程:

预处理$1到p$的阶乘即可，总时间复杂度：$O(p+lo{g}_{p}n\times p)$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second ll ksm(ll a,ll n,ll p){ ll ans=1; while(n){ if(n&1) ans=ans*a%p; a=a*a%p; n>>=1; } return ans; } ll fac[N]; int p; ll C(ll n,ll m){ //组合数&费马小定理. if(n<m) return 0; return fac[n]*ksm(fac[m]*fac[n-m]%p,p-2,p)%p; } ll Lucas(ll n,ll m){ //递归求解. if(!m) return 1; return C(n%p,m%p)*Lucas(n/p,m/p)%p; } int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d%d",&n,&m,&p); fac[0]=1; for(int i=1;i<=p;i++) fac[i]=fac[i-1]*i%p; printf("%lld\n",Lucas(n+m,n)); } return 0; }