BISHI70　【模板】组合数¶

中等通过率 39.84%python3样例通过牛客 AC

牛客原题　源码

讲解章节：组合数学

一句话

T 组询问，求 C(m, n) = m! / (n! (m-n)!) mod (1e9+7)。

解题思路¶

这题考什么¶

质模数下的组合数模板：预处理阶乘 + 阶乘逆元，O(1) 回答单次询问。

阶乘逆元的求法有两种：

每个都 pow(fact[i], P-2, P)：O(maxn log P)，5e5 次模幂太浪费；
倒推：先算 inv_fact[maxn] = pow(fact[maxn], P-2, P)，再用 inv_fact[i-1] = inv_fact[i] * i mod P （因为 1/(i-1)! = i / i!），一次模幂 + O(maxn) 乘法。这里用后者。

数据规模与复杂度¶

T <= 1e5，0 <= n <= m <= 5e5。

每次现算 O(n) 的连乘是 O(T*m) = 5e10，必死；
预处理 O(maxn) + 询问 O(1)，总 O(maxn + T)。

表只开到输入中出现的最大 m，样例里就只有 5。

P = 1e9+7 是质数且 P > maxn，所以 1..maxn 都与 P 互质，逆元全都存在，不需要 Lucas 定理（那是 m 超过模数时才要的）。

坑在哪¶

题面写的是 C_m^n，即「从 m 个里选 n 个」，n 是下标、m 是上标，别读反：样例 "2 4" 给的是 n=2, m=4，答案 C(4,2)=6；
边界 n=0 或 n=m 时答案 1，阶乘表里 fact[0]=1 已经覆盖；
一定要先把全部询问读进来求 max，再决定表长（否则要无脑开到 5e5）；
T 到 1e5，缓冲 IO 必需。

参考实现¶

solutions/BISHI70.py
import sys

P = 1000000007


def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    # 每组是「n m」两个数，用步长 2 的切片一次性拆成两列：
    # 下标 1、3、5… 是 n，下标 2、4、6… 是 m
    ns = [int(x) for x in data[1:1 + 2 * t:2]]
    ms = [int(x) for x in data[2:2 + 2 * t:2]]
    mx = max(ms) if ms else 0                   # 表只开到实际用到的最大上标

    # 阶乘表：fact[0] = fact[1] = 1 已由初值给出，从 2 开始递推
    fact = [1] * (mx + 1)
    for i in range(2, mx + 1):
        fact[i] = fact[i - 1] * i % P
    # 阶乘逆元表：先求出末项的逆元，再倒推，全程只有一次模幂
    inv_fact = [1] * (mx + 1)
    inv_fact[mx] = pow(fact[mx], P - 2, P)      # 只做一次模幂
    for i in range(mx, 0, -1):                  # 1/(i-1)! = i * (1/i!)
        inv_fact[i - 1] = inv_fact[i] * i % P

    out = []
    ap = out.append
    # C(m,n) = m! * (1/n!) * (1/(m-n)!)，三次查表两次乘法，每组 O(1)
    for n, m in zip(ns, ms):
        ap(str(fact[m] * inv_fact[n] % P * inv_fact[m - n] % P))
    sys.stdout.write("\n".join(out) + "\n")


main()

BISHI70 【模板】组合数¶