Lucas定理：

给出n,m,pn,m,pn,m,p，其中n∈[1,105],m∈[1,105],p∈[1,105],p∈primen\in[1,10^5],m\in[1,10^5],p\in[1,10^5],p\in primen∈[1,105],m∈[1,105],p∈[1,105],p∈prime
Cnm≡CnmodpmmodpC⌊np⌋⌊mp⌋(modp)C_{n}^m\ \equiv C_{n\ mod\ p}^{m\ mod\ p}C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor}\ (mod\ p) Cnm​ ≡Cn mod pm mod p​C⌊pn​⌋⌊pm​⌋​ (mod p)
其中第一个组合数直接暴力计算，第二个组合数递归计算

一些解释：

为何不能直接计算阶乘计算？

阶乘计算需要逆元，不是任何情况下都存在逆元的，考虑解不定方程求逆元，这样的限制最少，即解方程
ax≡1(modp)ax\equiv1\ (mod\ p) ax≡1 (mod p)
即解不定方程
ax−kp=1ax-kp=1 ax−kp=1
裴蜀定理，这个方程需要满足以下条件才会有解
gcd(a,k)=1gcd(a,k)=1 gcd(a,k)=1
可见并不是所有的a,ka,ka,k都满足这个条件的。

平时能用逆元是因为模数太大，nnn不超过模数，这样无论如何都存在逆元(1)(1)(1)

第一个组合数的计算方法：

此时nmodp

时间复杂度：O(p+logn)O(p+logn)O(p+logn)

#ifndef stdjudge
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll=long long;
const int N=1e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;ll qpow(ll a,ll b,ll p)
{ll ret=1,base=a;while(b){if(b&1) ret=ret*base%p;base=base*base%p;b>>=1;}return ret;
}ll inv(ll x,ll p){return qpow(x,p-2,p);}ll C(ll n,ll m,ll p)
{if(nret1=ret1*i%p;if(i<=m) ret2=ret2*i%p;if(i<=n-m) ret3=ret3*i%p;}return ret1*inv(ret2,p)%p*inv(ret3,p)%p;
}ll lucas(ll n,ll m,ll p)
{if(!n||!m) return 1;return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}int main()
{#ifdef stdjudgefreopen("in.txt","r",stdin);#endifint t; cin>>t;while(t--){ll n,m,p; cin>>n>>m>>p;cout<