给定 \(n,m,p\)，其中 \(n,m\) 较大，\(p\) 为质数且不是很大，求
\[\dbinom{n}{m}\bmod p \]\(\rm Lucas\) 定理
\[\dbinom{n}{m}\equiv\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\cdot \dbinom{n\bmod p}{m\bmod p}\pmod p（p 为质数） \]引理 \(1\)：
观察
\[\dbinom{p}{n}\equiv\dfrac{p!}{(p-n)!\cdot n!}\pmod p \]分子含有质因数 \(p\)，所以当分母不含质因数 \(p\) 时答案为 \(0\)。
否则，仅当 \(n=0\) 或 \(n=p\) 时分母也含有质因数 \(p\)，答案为 \(\dfrac{p!}{p!\cdot 0!}=1\)。
引理 \(2\)：
考虑这样一个式子
\[(a+b)^p \]根据二项式定理，这个就是
\[\sum\limits_{i=0}^{p}\dbinom{p}{i}a^i b^{p-i} \]由引理 \(1\)，只有 \(i=0\) 或 \(i=p\) 时 \(\dbinom{p}{i}\) 在模 \(p\) 的意义下值为 \(1\)，所以
\[\begin{aligned} (a+b)^p &\equiv a^0 b^p+a^p b^0\\ &\equiv a^p+b^p\pmod p \end{aligned} \]那么
\[(ax+by)^p\equiv a^p x^p+b^p y^p\pmod p \]由费马小定理得
\(a^p x^p+b^p y^p\equiv a x^p+b y^p\pmod p\)
就是说可以直接把指数 \(p\) 往里乘。
证明：
\((x+1)^n\) 中的项 \(x^m\) 的系数模 \(p\)，根据二项式定理就是 \(\dbinom{n}{m}\bmod p\)。\(\quad(1)\)
又根据引理 \(2\) 有
\[\begin{aligned} (x+1)^n &\equiv (x+1)^{p\left\lfloor\frac{n}{p}\right\rfloor}(x+1)^{n\bmod p}\\ &\equiv (x^p+1^p)^{\left\lfloor\frac{n}{p}\right\rfloor}(x+1)^{n\bmod p}\\ &\equiv (x^p+1)^{\left\lfloor\frac{n}{p}\right\rfloor}(x+1)^{n\bmod p}\pmod p \end{aligned} \]我们发现：
\((x^p+1)^{\left\lfloor\frac{n}{p}\right\rfloor}\) 中的各项的次数均为 \(p\) 的倍数。
\((x+1)^{n\bmod p}\) 中的各项的次数最多为 \(p-1\)。
注意到第 \(2\) 条，次数最多只能到 \(p-1\)，所以要想得到 \(x^m\)，只有一种方法：令 \(m=pq+r(r<p)\)，则在 \((x^p+1)^{\left\lfloor\frac{n}{p}\right\rfloor}\) 中取到 \(q\)（即 \(\left\lfloor\frac{m}{p}\right\rfloor\)）个 \(x^p\)，然后在 \((x+1)^{n\bmod p}\) 取到 \(r\)（即 \(m\bmod p\)）个 \(x\)。
方法数为 \(\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{q}\cdot\dbinom{n\bmod p}{r}\equiv\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\cdot\dbinom{n\bmod p}{m\bmod p}\pmod p\quad(2)\)
由 \((1)(2)\) 可得
\[\dbinom{n}{m}\equiv \dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\cdot \dbinom{n\bmod p}{m\bmod p}\pmod p \]证毕。
预处理处 \(\forall i\in[0,p)\)，\(i!\) 和 \(inv(i!)\)。然后对于单个询问，\(\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\) 部分递归去跑，因为 \(p\ge 2\)，所以是 \(\log n\) 的，\(\dbinom{n\bmod p}{m\bmod p}\) 部分就是预处理的。
时间复杂度为 \(\mathcal{O}(p+T\log n)\)，其中 \(T\) 为询问次数。
可以发现瓶颈在于线性的预处理，所以 \(p\) 不能太大。
\(\text{Code}\)
//18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 5;
int p;
int qpow(int a, int b)
{
int base = a, ans = 1;
while (b)
{
if (b & 1)
{
ans = (ll)ans * base % p;
}
base = (ll)base * base % p;
b >>= 1;
}
return ans;
}
int inv(int a)
{
return qpow(a, p - 2);
}
int fac[MAXN], inv_fac[MAXN];
void init()
{
fac[0] = 1;
for (int i = 1; i < p; i++)
{
fac[i] = (ll)fac[i - 1] * i % p;
}
inv_fac[p - 1] = inv(fac[p - 1]);
for (int i = p - 2; i >= 0; i--)
{
inv_fac[i] = (ll)inv_fac[i + 1] * (i + 1) % p;
}
}
int C(int n, int m)
{
if (m > n)
{
return 0;
}
return (ll)fac[n] * inv_fac[n - m] % p * inv_fac[m] % p;
}
int Lucas(int n, int m)
{
if (!m)
{
return 1;
}
return (ll)Lucas(n / p, m / p) * C(n % p, m % p) % p;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d%d", &n, &m, &p);
init();
printf("%d\n", Lucas(n + m, n));
}
return 0;
}