刷数论模板啦。。。
在正事之前发现了一个小知识：组合数有两种书写方式。一种是形如\(C_3^2\)，另一种是形如\(\binom{3}{2}\)。这两者等价。
卢卡斯定理其实也简单的：
\[\binom{m}{n}=\binom{m \mod p}{n \mod p} \times \binom{\lfloor \frac{m}{p} \rfloor }{ \lfloor \frac{n}{p} \rfloor} \mod p\]
这是一种简单的表达式。
lucas定理可以求大\(n,m\)的组合数取模。
这是一种递归的算法。下取整的大部分我们可以再次递归缩小范围求解，而取模的部分我们直接暴力来做。
如何暴力？
组合数的定义式：
\[C_m^n=\frac{m!}{n!(m-n)!}\]
在模意义下我们就没除法了。所以我们就要用到乘法逆元了。
我们先预处理出这些阶乘，然后可以用任意一种方法来求这两个阶乘的逆元。暴力乘上去即可。
代码：
#include<cstdio>
const int maxn = 1000005;
#define ll long long
ll n, m, p;
ll frac[maxn];
ll pow_mod(ll x, ll y, ll p)
{
ll ans = 1, base = x % p;
while(y)
{
if(y & 1) ans = ans * base % p;
base = base * base % p;
y >>= 1;
}
return ans % p;
}
ll inv(ll x, ll p)
{
return pow_mod(x, p - 2, p) % p;
}
ll C(ll x, ll y, ll p)
{
if(x < y) return 0;
return frac[x] * inv(frac[y], p) % p * inv(frac[x - y], p) % p;
}
ll lucas(ll x, ll y, ll p)
{
if(y == 0) return 1;
return C(x % p, y % p, p) * lucas(x / p, y / p, p) % p;
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%lld%lld%lld", &n, &m, &p);
frac[0] = 1;
for(int i = 1; i <= p; i++) frac[i] = frac[i - 1] * i % p;
printf("%lld\n", lucas(n + m, n, p));
}
return 0;
}