BISHI71　人员分组问题¶

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

牛客原题　源码

讲解章节：组合数学

一句话

从 n 人中选出恰好 5~7 人的小组，求方案数 mod (1e9+7)。

解题思路¶

这题考什么¶

组合数的直接应用：答案 = C(n,5) + C(n,6) + C(n,7)。「恰好 5∼7 人」是三种互斥情形，加法原理相加即可。

因为下标固定只有 5、6、7 三个，完全不必预处理 1e6 的阶乘表，用下降阶乘直接算就行：

C(n,k) = n(n-1)...(n-k+1) / k!

分母 k! ∈ {120, 720, 5040} 都远小于 P 且与 P 互质，乘上它的逆元即可。

数据规模与复杂度¶

n <= 1e6，单组数据。本做法 O(1)（最多 7 次乘法 + 3 次求逆），比预处理 1e6 阶乘表还快，内存也是 O(1)。 Python 3.9 其实有 math.comb(n, k)，能算精确大整数再取模；n=1e6、k=7 时分子约 42 位，也完全可行，但模意义下的写法才是这类题的通用姿势。

坑在哪¶

n < 5 时答案为 0（样例 n=1 就是 0）；n = 5/6 时只有前一两项非零。所以 comb() 里必须先判 n < k 直接返回 0：否则下降阶乘会算出 6543210 这种带 0 的乘积（结果碰巧也是 0），甚至出现负因子，虽然模意义下仍正确，但显式判掉更清楚；
逆元：P 是质数，用 pow(k_fact, -1, P)（Python 3.8+ 支持负指数求逆元， 3.9 同样可用）或 pow(k_fact, P-2, P)，两者等价；
别忘了对最终和再取一次模。

参考实现¶

solutions/BISHI71.py
import sys

P = 1000000007


def comb(n: int, k: int) -> int:
    """C(n,k) mod P，k 很小时的 O(k) 写法；n < k 时返回 0。"""
    if n < k:
        return 0                        # 人数不够，一种都选不出来
    num = 1
    for i in range(k):                  # 下降阶乘 n(n-1)...(n-k+1)，共 k 个因子
        num = num * (n - i) % P
    den = 1
    for i in range(1, k + 1):           # k! 最大只有 5040，不必取模
        den *= i
    return num * pow(den, -1, P) % P     # Python 3.8+：负指数 = 扩展欧几里得求逆元


n = int(sys.stdin.buffer.read().split()[0])
# 「恰好 5~7 人」是三种互斥情形，方案数相加；末尾再取一次模防止和越过 P
sys.stdout.write(str((comb(n, 5) + comb(n, 6) + comb(n, 7)) % P) + "\n")

BISHI71 人员分组问题¶