Lucas 定理

若 $p$ 为质数，则有：
$$\binom{n}{m} = \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \times \binom{n \bmod p}{m \bmod p}$$

不想证了。
Lucas 定理一般适用于 $p$ 较小的问题。
注意到后者保证了组合数的两个参数都在 $[0,p)$，就可以通过阶乘 $O(1)$ 得到；对于前者考虑用递归的方式求解，由于有除法运算，最多只会递归 $O(\log V)$ 层。
因此总复杂度 $O(\log V)$，其中 $v$ 为值域。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, m, p;

int qmi(int a, int k) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = res * 1ll * a % p;
        a = a * 1ll * a % p, k >>= 1;
    }
    return res;
}

int fac[N], inv[N];
void init() {
    fac[0] = 1;
    for (int i = 1; i < p; i++) fac[i] = fac[i - 1] * 1ll * i % p;
    inv[p - 1] = qmi(fac[p - 1], p - 2);
    for (int i = p - 2; i >= 0; i--) inv[i] = inv[i + 1] * 1ll * (i + 1) % p;
}
inline int C(int n, int m) { if (n < m) return 0; return fac[n] * 1ll * inv[m] % p * 1ll * inv[n - m] % p; }
inline int lucas(int n, int m) {
    if (n < m) return 0;
    if (!n || !m) return 1;
    return C(n % p, m % p) * 1ll * lucas(n / p, m / p) % p;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &p), n += m;
        if (p == 1) puts("0");
        else {
            init();
            printf("%lld\n", lucas(n, m) );
        }
    }
    return 0;
}