思路与算法

利用整数恒等式

本题 $m\le10^4$，即使 $n$ 很大，也只需计算分子和分母各 $m$ 项的模积。因为 $p$ 是素数且 $m<p$，分母 $m!$ 的每个因子都非零模 $p$，所以分母可逆。费马小定理给出

用二进制快速幂计算这个逆元，再与分子模积相乘。

不能直接套需要 $n<p$ 的 $n!/(m!(n-m)!)$ 模逆元模板，因为本题允许 $n\ge p$。改用长度为 $m$ 的连乘后，只有分母需要可逆；若分子包含 $p$ 的倍数，结果自然为0。逐个处理 $T$ 组查询。

正确性说明

组合数乘积恒等式在整数上成立，即 $m!\binom nm=(n-m+1)\cdots n$。对 $p$ 取模后，因 $m<p$ 且 $p$ 素，$m!$ 与 $p$ 互质，可以在同余式两侧乘其逆元，得到程序使用的公式。费马小定理保证非零分母的 $p-2$ 次幂就是逆元，包括 $p=2$ 时指数0的边界。二进制快速幂正确计算该幂，逐步取模保持乘积余数，因此每组输出均为组合数的余数；证明不要求 $n<p$。

复杂度

单组初始化为 $O(1)$，两组连乘为 $O(m)$，模幂为 $O(\log p)$，总时间 $O(m+\log p)$；全部查询为 $O(T+\sum_q(m_q+\log p_q))$。额外空间 $O(1)$，不预处理到 $n$ 或 $p$，也不构造巨大的精确组合数。

易错点

1. 可逆条件是 $m<p$ 且 $p$ 素，不能把分子非零作为前提；分子为0时结果就是0。
2. $n\ge p$ 时不要给 $n!$ 求逆。此题输入为 $n,m,p$，不是某些Lucas题中的 $n+m,m,p$。
3. 模数2、$m=n$、$n$ 跨越模数、最大 $m$ 均已覆盖。源称“正整数”，但模余数可以为0，不能输出 $p$ 代替0。
4. 模内乘积小于 $10^{18}$，使用64位并在每次乘法后取模。
5. 独立答案以任意精度整数的精确组合数再取模获得，并与小规模Pascal三角核对；训练数据非官方原版。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll power(ll a, ll b, ll mod) {
    ll answer = 1 % mod;
    while (b) {
        if (b & 1)
            answer = answer * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return answer;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tests;
    cin >> tests;
    while (tests--) {
        ll n, m, p;
        cin >> n >> m >> p;
        ll numerator = 1, denominator = 1;
        for (ll i = 1; i <= m; i++) {
            numerator = numerator * ((n - m + i) % p) % p;
            denominator = denominator * i % p;
        }
        cout << numerator * power(denominator, p - 2, p) % p << '\n';
    }
}