对于质数 \(p\)，有
\[{\Large \begin{aligned} & \binom{n}{m} \equiv \binom{\left \lfloor n/p \right \rfloor }{\left \lfloor m/p \right \rfloor } \binom{n\mod{p}}{m\mod p} \pmod{p} \end{aligned} } \]引理1
\[{\Large \begin{aligned} & \binom{p}{n}\mod{p}=[n=0\vee n=p] \end{aligned} } \]引理2
\[{\Large \begin{aligned} & (a+b)^p \equiv a^p+b^p \pmod{p} \end{aligned} } \]P3807 【模板】卢卡斯定理/Lucas 定理
直接应用上面的。\(n、m\)较小时就可以直接暴力求。由于每个 \(p\) 不同，因此不能预处理阶乘。
又因为 \(p\) 可能比 \(n、m\) 小，因此不能递推求逆元。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p,cnt;
int ksm(int x,int k)
{
int res=1;
while(k)
{
if(k&1) res=res*x%p;
k>>=1;x=x*x%p;
}
return res;
}
int C(int n,int m)
{
int jie1=1,jie2=1;
for(int i=n;i>=n-m+1;i--) jie1=jie1*i%p;
for(int i=1;i<=m;i++) jie2=jie2*i%p;
jie2=ksm(jie2,p-2);return jie1*jie2%p;
}
int lucas(int n,int m)
{
if(m==0) return 1;
return (C(n%p,m%p)*lucas(n/p,m/p))%p;
}
void solve()
{
int n,m;cin>>n>>m>>p;n=n+m;cnt=0;
cout<<lucas(n,m)<<'\n';
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;cin>>T;while(T--) solve();
}