1650：【例 3】组合

题目描述

给出组合数 $C(n,m)$ 表示从 $n$ 个元素中选出 $m$ 个元素的方案数。例如 $C(5,2)=10, C(4,2)=6$。可是当 $n,m$ 比较大的时候，$C(n,m)$ 很大。于是 xiaobo 希望你输出 $C(n,m) \bmod p$ 的值。

输入格式

输入数据第一行是一个正整数 $T$，表示数据组数；

接下来是 $T$ 组数据，每组数据有 $3$ 个正整数 $n, m, p$。

输出格式

对于每组数据，输出一个正整数，表示 $C(n,m) \bmod p$ 的结果。

样例

样例输入 #1

2
5 2 3
5 2 61

样例输出 #1

1
10

样例解释 #1

• 第一组：$C(5,2)=10$，$10 \bmod 3 = 1$。
• 第二组：$C(5,2)=10$，$10 \bmod 61 = 10$。

数据范围

对于所有数据：

• $1 \le m \le n \le 10^9$
• $m \le 10^4$
• $m < p < 10^9$
• $p$ 是素数

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：$n$ 很大，但 $m$ 较小（$\le 10^4$），且 $p$ 是素数。可以用组合数公式：

$$C(n,m) = \frac{n!}{m!(n-m)!} = \frac{n \cdot (n-1) \cdots (n-m+1)}{m!}$$

因为 $m$ 不大，可以直接计算分子乘积模 $p$，再乘以分母的逆元（模 $p$）。由于 $p$ 是素数，可以用费马小定理求逆元。

但需要注意：如果 $n, m$ 很大，但 $p$ 可能小于 $n$，此时 $n!$ 中可能包含 $p$ 的因子，导致分母的逆元不存在（因为分母可能与 $p$ 不互质）。但题目保证 $m < p$，且 $p$ 是素数，所以 $m!$ 中的因子都不包含 $p$（因为 $m < p$），所以 $m!$ 与 $p$ 互质，其逆元存在。然而分子 $n \cdot (n-1) \cdots (n-m+1)$ 中可能包含 $p$ 的倍数，此时乘积模 $p$ 可能为 $0$，但实际组合数可能不被 $p$ 整除？例如 $C(p,1) = p$，模 $p$ 为 $0$。所以我们需要处理分子中 $p$ 的因子。

由于 $p$ 是素数，且 $m < p$，所以分母 $m!$ 不含 $p$。分子是连续 $m$ 个整数的乘积，如果这 $m$ 个数中包含 $p$ 的倍数，则组合数模 $p$ 为 $0$？不一定，因为组合数可能是整数，可能约分后消去 $p$。例如 $C(2p, 2) = \frac{2p(2p-1)}{2} = p(2p-1)$，模 $p$ 为 $0$。但 $C(p+1, 2) = \frac{(p+1)p}{2}$，分子含 $p$，但分母 $2$ 与 $p$ 互质，所以组合数模 $p$ 为 $0$（因为 $p$ 整除组合数）。所以当分子中包含 $p$ 的倍数时，组合数模 $p$ 可能为 $0$。

更一般地，组合数 $C(n,m)$ 模素数 $p$ 可以用 Lucas 定理 计算，但 Lucas 定理适用于 $p$ 较小的情况（因为需要计算 $n_i, m_i$ 模 $p$ 的组合数）。这里 $p$ 可以很大（$<10^9$），但 $m$ 较小（$\le 10^4$），且 $p > m$，所以我们可以直接使用公式计算，但需要处理分子中 $p$ 的因子。

因为 $p$ 是素数，分子中最多有一个 $p$ 的倍数（因为连续 $m$ 个数中，$p$ 的倍数最多 $\lfloor m/p \rfloor$ 个，但 $m < p$，所以最多 $1$ 个）。设分子中第 $i$ 项 $n-i+1$ 是 $p$ 的倍数，则该项模 $p$ 为 $0$，整个乘积模 $p$ 为 $0$。但组合数可能约分后不为 $0$？例如 $C(p,1)=p$，模 $p$ 为 $0$。$C(p,2)=p(p-1)/2$，模 $p$ 为 $0$。所以如果分子中包含 $p$ 的倍数，则组合数模 $p$ 为 $0$。因为分母 $m!$ 不含 $p$，无法约掉 $p$。所以结论：如果 $n, n-1, ..., n-m+1$ 中存在 $p$ 的倍数，则 $C(n,m) \equiv 0 \pmod{p}$。

否则，分子与 $p$ 互质，我们可以直接计算分子模 $p$，再乘以分母的逆元。

因此，算法步骤：

1. 读入 $T$。
2. 对于每组数据，读入 $n, m, p$。
3. 检查 $n, n-1, ..., n-m+1$ 中是否存在 $p$ 的倍数。由于 $m \le 10^4$，可以枚举这 $m$ 个数，但 $n$ 可能很大，我们不能直接生成这些数。我们可以计算 $n \bmod p$，然后看区间 $[n-m+1, n]$ 是否包含 $p$ 的倍数。即是否存在整数 $k$ 使得 $n-m+1 \le kp \le n$。这等价于 $\lceil (n-m+1)/p \rceil \le \lfloor n/p \rfloor$。如果成立，则存在 $p$ 的倍数，输出 $0$。
4. 否则，计算分子 $num = \prod_{i=0}^{m-1} (n-i) \bmod p$。因为 $m \le 10^4$，可以直接循环 $m$ 次，每次乘 $(n-i)$ 并取模 $p$。
5. 计算分母 $den = m! \bmod p$，同样循环计算。
6. 计算 $den$ 的逆元 $inv$（因为 $p$ 是素数，可以用费马小定理：$inv = den^{p-2} \bmod p$）。
7. 输出 $num \times inv \bmod p$。

注意：$n$ 可能小于 $m$，但题目保证 $m \le n$，所以 $n \ge m$。

由于 $p$ 可能很大（$<10^9$），快速幂求逆元需要 $O(\log p)$，总复杂度 $O(T \cdot (m + \log p))$，可以接受。

但检查是否存在 $p$ 的倍数时，需要注意整数溢出。可以用以下方法：

• 设 $low = n - m + 1$，$high = n$。
• 如果 $low \le 0$，则区间包含负数，但 $p$ 是正数，所以 $p$ 的倍数可能是负数？但组合数定义中 $n, m$ 为正整数，$n-i$ 都是正整数（因为 $i < m \le n$），所以 $low \ge 1$。实际上 $n \ge m$，所以 $n-m+1 \ge 1$。
• 计算 $first = \lceil low/p \rceil \cdot p$，如果 $first \le high$ 且 $first \ge low$，则存在 $p$ 的倍数。

由于 $p$ 可能很大，直接用除法判断：

if (n / p != (n-m) / p)  // 因为 (n-m) 即 n-m+1-1，注意区间是 [n-m+1, n]

更精确地：设 $a = n-m+1$, $b = n$。如果 $\lfloor b/p \rfloor > \lfloor (a-1)/p \rfloor$，则存在 $p$ 的倍数。即 if (b/p > (a-1)/p)。

但注意整数除法下取整。

因此，检查代码：

long long a = n - m + 1;
if (n / p != (a-1) / p) {
    // 存在 p 的倍数
    cout << 0 << endl;
}

注意：$n, m, p$ 都是 long long 范围。

如果不存在 $p$ 的倍数，则计算分子分母。

但 $m$ 最大 $10^4$，循环 $m$ 次乘法取模是可行的。

注意：$p$ 是素数，但 $p$ 可能很小（大于 $m$ 但可能接近 $m$），但 $m < p$，所以 $p$ 至少为 $m+1$。

因此，完整算法：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll pow_mod(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m, p;
        cin >> n >> m >> p;
        ll a = n - m + 1;
        // 检查区间 [a, n] 中是否存在 p 的倍数
        if (n / p != (a-1) / p) {
            cout << 0 << endl;
            continue;
        }
        // 计算分子
        ll num = 1;
        for (ll i = 0; i < m; i++) {
            num = num * (n - i) % p;
        }
        // 计算分母 m!
        ll den = 1;
        for (ll i = 1; i <= m; i++) {
            den = den * i % p;
        }
        // 求逆元
        ll inv = pow_mod(den, p-2, p);
        ll ans = num * inv % p;
        cout << ans << endl;
    }
    return 0;
}

但需要注意：当 $p$ 很大时，$p-2$ 可能很大，快速幂需要 $O(\log p)$，可以接受。

此外，如果 $m$ 很小，但 $p$ 非常大，循环 $m$ 次乘法没问题。

注意：上述检查存在 $p$ 的倍数的方法是否总是正确？考虑 $a=1, n=5, p=3$，区间 $[1,5]$ 包含 $3$，$n/p=1, (a-1)/p=0$，不等，正确。考虑 $a=3, n=5, p=3$，区间 $[3,5]$ 包含 $3$，$n/p=1, (a-1)/p=0$，不等。考虑 $a=4, n=5, p=3$，区间 $[4,5]$ 不含 $3$ 的倍数，$n/p=1, (a-1)/p=1$，相等。所以条件正确。

特殊情况：当 $m=0$？题目 $m\ge 1$，不考虑。

注意：当 $p$ 很大时，$n/p$ 和 $(a-1)/p$ 可能相等，即使区间包含 $p$ 的倍数？例如 $p=10^9+7$，区间长度 $m \le 10^4$，如果 $p$ 远大于 $n$，则区间内不可能有 $p$ 的倍数，所以条件成立。所以检查是安全的。