第 84 章　组合数学

配套例题：BISHI70 【模板】组合数、BISHI69 [HNOI2008] 越狱、BISHI71 人员分组问题、 BISHI67 穿搭大挑战、BISHI66 子数列求积 来源：S3 day10《PJ-7-2 计数原理》《TG-8-2 组合数》（rxz）、《组合数学》（loriex）、 《NOIP 组合数学、数论选讲》（Colin）；day9 resource《数论》（邹雨恒）第 44–61 页、 《数论与信息学竞赛》（胡渊鸣）第 33–34 页 前置：81-快速幂与逆元、80-数论基础

组合数学在笔试里的出现频率极高，而且大部分题的难点不在算，而在数对。 这一章按「计数原理 → 组合数 → 组合数取模 → 经典数列」的顺序展开。

---

84.1　两个计数原理

rxz 的《计数原理》课件用最朴素的例子讲清楚了这两条：

加法原理：假设您有很多种手段，使用每种手段都可以达成目标。 那么：每种手段的方法数之和，就是达成目标的方法数。

乘法原理：如果您为了达成目标，需要几个步骤，所有的步骤都需要完成，目标才能达成。 那么完成目标的方法数是：各步骤方法数的乘积。

课件还强调了它们的区别：

乘法原理中，各步骤是独立的；加法原理中，各手段只能用其中一个。

原理	关键词	中文提示
加法	分类、互斥	「或者」
乘法	分步、独立	「并且」

课件的混合例题很有代表性：

rxz 要到哈尔滨读书去。可以直接飞过去（5 趟航班）， 也可以先去上海（7 趟）再去哈尔滨（2 趟）。 答案：\(5 + 7\times2 = 19\)。

用加法原理的前提是「互斥」。如果两类方案有重叠，就要用容斥（84.9）。

---

84.2　排列与组合

排列数

从 \(n\) 个不同元素中取 \(m\) 个排成一列：

\[A_n^m = n(n-1)\cdots(n-m+1) = \frac{n!}{(n-m)!}\]

（乘法原理：第一位 \(n\) 种，第二位 \(n-1\) 种，……）

组合数

从 \(n\) 个不同元素中取 \(m\) 个不计顺序：

\[\binom nm = C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!\,(n-m)!}\]

除以 \(m!\) 的理由：同一个 \(m\) 元子集对应 \(m!\) 种不同排列， 所以排列数是组合数的 \(m!\) 倍。这是「先排后除」的标准套路。

约定：\(m<0\) 或 \(m>n\) 时 \(\binom nm = 0\)；\(\binom n0 = \binom nn = 1\)。 写代码时把这两条兜住，能省掉一大堆边界判断。

常用恒等式

恒等式	组合意义 / 证明
\(\binom nm = \binom n{n-m}\)	选 \(m\) 个 \(\iff\) 扔掉 \(n-m\) 个
\(\binom nm = \binom{n-1}{m-1}+\binom{n-1}{m}\)	杨辉恒等式：按「第 \(n\) 个元素选不选」分类
\(m\binom nm = n\binom{n-1}{m-1}\)	数「(集合, 集合中的一个特定元素)」对，两种数法
\(\sum_{k=0}^{n}\binom nk = 2^n\)	子集总数
\(\sum_{k=0}^{n}(-1)^k\binom nk = 0\ (n\ge1)\)	二项式定理取 \(x=-1\)
\(\sum_{k}\binom mk\binom n{r-k} = \binom{m+n}r\)	范德蒙德卷积：从 \(m\) 男 \(n\) 女中选 \(r\) 人
\(\sum_{i=r}^{n}\binom ir = \binom{n+1}{r+1}\)	曲棍球恒等式（杨辉三角斜线求和）
\(\sum_{k}\binom nk^2 = \binom{2n}n\)	范德蒙德取 \(m=n,r=n\)

TG 课件的「求和 II / 求和 III」两页问的就是杨辉三角某一行和某条斜线的和， 答案分别是上表的第 4 条和第 7 条。

杨辉三角

n=0:                1
n=1:              1   1
n=2:            1   2   1
n=3:          1   3   3   1
n=4:        1   4   6   4   1
n=5:      1   5  10  10   5   1

递推 \(\binom nm = \binom{n-1}{m-1}+\binom{n-1}m\)，边界 \(\binom n0 = 1\)。

# [片段] 模板：杨辉三角 O(n²) 预处理组合数（n <= 2000 时最省心）
def pascal(n, MOD=None):
    """C[i][j] = C(i, j)，i, j <= n。MOD 为 None 时算精确大整数。"""
    # 全 0 初始化：右上三角（j > i）永远不会被赋值，正好对应 C(i, j) = 0
    C = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        C[i][0] = 1                       # 边界：一个都不选，只有 1 种方案
        for j in range(1, i + 1):         # 只填到 j = i，越界的列留 0
            # 杨辉恒等式：按「第 i 个元素选不选」把方案分成互斥的两类
            v = C[i - 1][j - 1] + C[i - 1][j]
            # 全程只有加法，所以任意模数都能用；MOD 为 None 时留精确大整数
            C[i][j] = v % MOD if MOD else v
    return C

杨辉三角的最大优势：模数可以是任意数，甚至不是质数—— 因为整个过程只有加法，不需要除法、不需要逆元。 模数是合数（比如 \(10^6\)、\(100003\) 这种非质数）且 \(n\le2000\) 时，首选杨辉三角。

Python 现实性：\(O(n^2)\) 次纯 Python 循环，\(n=2000\) 是 \(2\times10^6\)，约 1 秒，勉强； \(n=5000\) 就是 \(1.25\times10^7\)，必然超时。上限 \(n\le2000\)。

---

84.3　二项式定理

\[(a+b)^n = \sum_{k=0}^{n}\binom nk a^{n-k}b^k\]

证明（组合意义）：把 \((a+b)^n\) 展开成 \(n\) 个因子相乘， 每个因子选 \(a\) 或选 \(b\)。选出 \(k\) 个 \(b\) 的方案数是 \(\binom nk\)， 每种方案贡献 \(a^{n-k}b^k\)。\(\square\)

常用特例：

代入	结果
\(a=b=1\)	\(\sum_k\binom nk = 2^n\)
\(a=1, b=-1\)	\(\sum_k(-1)^k\binom nk = 0\)（\(n\ge1\)）
\(a=1, b=2\)	\(\sum_k\binom nk 2^k = 3^n\)

TG 课件那页写着「1024」的例题就是 \(\sum_{k}\binom{10}k = 2^{10} = 1024\)。

课件还预告了两条后路：「将来泥萌会学到母函数（生成函数）」 「将来泥萌会在概率论中学到二项分布」。 生成函数是把组合恒等式变成多项式运算的通用工具，见 24-多项式。

---

84.4　组合数取模：按数据范围选算法

这是本章最考「选型」的一节。loriex 和邹雨恒的课件都是按范围一档档往上讲的。

范围	做法	复杂度	对模数的要求
\(n,m \le 2000\)，询问多	杨辉三角打表	\(O(n^2)\) – \(O(1)\)	任意模数
\(n,m \le 5\times10^5\)，询问多，\(P\) 质数且 \(P>n\)	阶乘表 + 阶乘逆元	\(O(n)\) – \(O(1)\)	\(P\) 质数
\(n\) 巨大但 \(m\) 很小（\(\le 100\)）	下降阶乘 + 一次求逆	\(O(m)\)	\(\gcd(m!,P)=1\)
\(n,m \le 10^{18}\)，\(P\) 质数且 \(P\) 较小	Lucas 定理	\(O(P + \log_P n)\)	\(P\) 质数
\(P = p^k\) 或一般合数	扩展 Lucas + CRT	复杂	任意

阶乘 + 阶乘逆元（最常用）

\[\binom nm = n!\cdot (m!)^{-1}\cdot ((n-m)!)^{-1} \pmod P\]

阶乘逆元用倒推法，全程只做一次模幂（推导见 81-快速幂与逆元 的 81.6）：

\[\operatorname{invfact}[i-1] = \operatorname{invfact}[i]\times i\]

模板一：组合数预处理（阶乘表 + 逆元倒推）

# [片段] 模板：质模数下的组合数，O(n) 预处理 + O(1) 查询
P = 10 ** 9 + 7


def build_comb(n, P=P):
    """返回闭包 C(a, b)。要求 P 是质数且 P > n。只做一次模幂。"""
    # 阶乘表：fact[i] = i! mod P。fact[0] = fact[1] = 1 由初值直接给出，
    # 所以循环从 2 开始；每步立刻取模，数值始终小于 P，乘法恒为常数时间
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i - 1] * i % P
    # 阶乘逆元表：只有下标 n 这一项花一次模幂，其余靠倒推
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], P - 2, P)          # ★ 唯一的一次模幂
    for i in range(n, 0, -1):
        # 由 1/(i-1)! = i * (1/i!) 倒着递推，n 次乘法换掉 n 次模幂
        inv_fact[i - 1] = inv_fact[i] * i % P     # 1/(i-1)! = i * (1/i!)

    def C(a, b):
        # b > a 时组合数按定义就是 0；不拦住的话 a - b 变负，
        # inv_fact[a - b] 会取到表尾的元素，静默算出一个错误答案
        if b < 0 or b > a or a < 0:
            return 0                              # ★ 兜住所有非法参数
        # C(a, b) = a! * (b!)^(-1) * ((a-b)!)^(-1)，三次查表 + 两次乘法
        return fact[a] * inv_fact[b] % P * inv_fact[a - b] % P

    return C, fact, inv_fact

为什么必须 \(P > n\)？ 否则 \(P! \equiv 0\)，阶乘表从下标 \(P\) 开始全是 0，逆元不存在。 遇到 \(P \le n\) 的情况就要上 Lucas。

下降阶乘：\(m\) 很小的情形

\[\binom nm = \frac{n(n-1)\cdots(n-m+1)}{m!}\]

只要 \(O(m)\) 次乘法加一次求逆，不需要开 \(10^6\) 的表：

# [片段] 模板：m 很小时的 O(m) 组合数
def comb_small(n, m, P):
    """C(n, m) mod P，m 很小时用。要求 gcd(m!, P) = 1。"""
    if m < 0 or n < m:
        return 0                        # 定义如此，也避免下面乘出负因子
    # 分子是下降阶乘 n(n-1)...(n-m+1)，恰好 m 项，所以循环 m 次
    num = 1
    for i in range(m):
        num = num * (n - i) % P         # 每项先取模，n 再大也不会膨胀
    # 分母是 m!；m 很小（题面保证 <= 100 量级），精确算完再求一次逆元
    den = 1
    for i in range(1, m + 1):
        den *= i                        # m 小，m! 直接精确算
    # 只求一次逆元：先把分子分母各自乘完，再做一次除法
    return num * pow(den, -1, P) % P    # Python 3.8+ 负指数 = 求逆元

Lucas 定理

定理（Lucas）：\(p\) 为质数，把 \(n, m\) 写成 \(p\) 进制 \(n=(n_kn_{k-1}\cdots n_0)_p\)、\(m=(m_km_{k-1}\cdots m_0)_p\)，则 $\(\binom nm \equiv \prod_{i=0}^{k}\binom{n_i}{m_i} \pmod p\)$ 若某位 \(n_i < m_i\)，则 \(\binom nm \equiv 0 \pmod p\)。

证明思路：在 \(\mathbb{F}_p[x]\) 中，\((1+x)^p \equiv 1 + x^p \pmod p\) （因为 \(\binom pi\) 对 \(0<i<p\) 都被 \(p\) 整除）。 于是 \((1+x)^n = (1+x)^{n_0}\left((1+x)^{p}\right)^{\lfloor n/p\rfloor} \equiv (1+x)^{n_0}\left(1+x^p\right)^{\lfloor n/p\rfloor}\)。 比较 \(x^m\) 的系数：\(m\) 的贡献唯一地拆成「低位 \(m_0\) 来自第一个因子」+ 「高位来自第二个因子」，即 \(\binom nm \equiv \binom{n_0}{m_0}\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\)， 递归展开即得。\(\square\)

等价的递归形式（loriex 课件的写法）：

\[\binom nm \bmod p = \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\cdot\binom{n\bmod p}{m\bmod p} \bmod p\]

模板二：Lucas 定理

# [片段] 模板：Lucas 定理，p 为质数且 p 较小（<= 1e6）
def build_lucas(p):
    """预处理 0..p-1 的阶乘与阶乘逆元，返回 lucas(n, m)。"""
    # 表只开到 p-1：Lucas 把大组合数拆成若干个「上下标都小于 p」的小组合数，
    # 表长由模数 p 决定，与 n、m 的大小无关，这正是 Lucas 的价值
    fact = [1] * p
    for i in range(1, p):
        fact[i] = fact[i - 1] * i % p
    inv_fact = [1] * p
    inv_fact[p - 1] = pow(fact[p - 1], p - 2, p)   # 唯一的一次模幂（费马小定理，p 为质数）
    for i in range(p - 1, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % p      # 1/(i-1)! = i * (1/i!)

    def small_C(a, b):
        """a, b 都在 [0, p) 内的组合数，直接查表。"""
        if b < 0 or b > a:
            return 0                 # 对应 Lucas 里「某一位 n_i < m_i」的情形
        return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p

    def lucas(n, m):
        """C(n, m) mod p，n, m 可以大到 1e18。"""
        res = 1
        # 每轮取出 n、m 的一个 p 进制位并相乘；m 变成 0 时高位的 m_i 全为 0，
        # 而 C(n_i, 0) = 1，剩下的位不影响乘积，所以循环条件是 m 而不是 n
        while m:
            res = res * small_C(n % p, m % p) % p
            if res == 0:
                return 0                 # 某一位 n_i < m_i，提前退出
            n //= p                       # 右移一个 p 进制位
            m //= p
        return res

    return lucas

复杂度 \(O(p)\) 预处理 + 每次询问 \(O(\log_p n)\)。 \(p = 10^5\) 时预处理十万项，每次询问只要 \(\log_{10^5}10^{18} \approx 4\) 次查表。

什么时候才用 Lucas？ 判据只有一条：\(n\) 或 \(m\) 超过了模数 \(p\)。 此时阶乘表里 \(p! \equiv 0\)，\(p\) 及以后的阶乘逆元根本不存在， 「阶乘表 + 逆元倒推」整个失效。反过来，只要 \(P > n\)（例如 \(P=10^9+7\) 而 \(n \le 5\times10^5\)）， Lucas 除了拖慢常数没有任何好处。

Lucas 还要求 \(p\) 是质数且 \(p\) 不太大（要开 \(O(p)\) 的表）。 \(p\) 是质数的幂或一般合数时，得先按 \(p = \prod p_i^{k_i}\) 分别用扩展 Lucas 求出各个分量， 再用中国剩余定理（CRT，把若干个互质模数下的同余条件合并成一个）拼回去， 见 114-同余方程组与离散对数。

Python 的内置组合数：math.comb

Python 3.8+ 提供了 math.comb(n, k) 和 math.perm(n, k)：

>>> import math
>>> math.comb(5, 2)          # 10
>>> math.perm(5, 2)          # 20
>>> math.comb(50, 25)        # 126410606437752   —— 精确大整数

场景	能不能用 math.comb
求精确值、\(n\) 不大	✅ 最省事
\(n\) 大但 \(k\) 很小（如 \(n=10^6,k=7\)）	✅ 分子只有 40 多位，很快
\(n=5\times10^5\)、\(k\approx n/2\)、要取模	❌ 中间的大整数有 \(1.5\times10^5\) 位，一次就要几十毫秒
\(T=10^5\) 次询问且要取模	❌ 必须预处理阶乘表

判断口诀：math.comb 算的是精确大整数，代价随 \(\min(k, n-k)\) 的增大而爆炸。 只要题目给了模数且 \(k\) 可能很大，就老老实实建阶乘表。 参见 22-高精度与大整数。

---

84.5　捆绑法与隔板法

rxz 的课件把这两个技巧讲得很清楚（最后一页还提醒：「一定要看清问题！不要乱用」）。

捆绑法：要求某些元素相邻

8 个讲师排成一排，要求 rxz 和 zcy 站在一起（谁前谁后都行），有多少方案？

把两人捆成一个整体，于是变成 7 个「元素」的全排列 \(7!\)， 再乘上内部的 \(2!\) 种顺序：

\[7! \times 2! = 5040\times2 = 10080\]

插空法：要求某些元素不相邻

8 个讲师排成一排，但禁止 rxz 和 zcy 站在一起。

先排其余 6 人（\(6!\) 种），产生 7 个空位（含两端），把两人放进不同的空位（\(A_7^2\)）：

\[6!\times A_7^2 = 720\times42 = 30240\]

验算：\(8! - 10080 = 40320-10080 = 30240\) ✓（正难则反同样能算）。

术语提醒：rxz 的课件把上面这个「插空法」标成了「隔板法」。 在通行的中文教材里，隔板法（stars and bars）指的是下面这个， 两者不是一回事，做题时别混。

隔板法：相同物品分组

\(n\) 个相同的球分给 \(k\) 个不同的人：

条件	公式	推导
每人至少 1 个	\(\binom{n-1}{k-1}\)	\(n\) 个球排成一排产生 \(n-1\) 个缝，插 \(k-1\) 块板
允许有人拿 0 个	\(\binom{n+k-1}{k-1}\)	先给每人预支 1 个，转化为上一种：\(\binom{n+k-1}{k-1}\)
第 \(i\) 人至少 \(a_i\) 个	\(\binom{n-\sum a_i+k-1}{k-1}\)	先发下界，再套上一条

这也是「不定方程 \(x_1+\cdots+x_k=n\) 的非负整数解个数」的标准答案。

---

84.6　鸽巢原理

鸽巢（抽屉）原理：把 \(n+1\) 个物品放进 \(n\) 个抽屉，必有一个抽屉放了至少 2 个。

加强版：把 \(n\) 个物品放进 \(k\) 个抽屉，必有一个抽屉放了至少 \(\lceil n/k\rceil\) 个。

竞赛里的典型用法：

题型	抽屉是什么
「必存在两个数模 \(n\) 同余」	\(n\) 个余数
「必存在一段连续和被 \(n\) 整除」	前缀和的 \(n\) 个余数（\(n+1\) 个前缀）
「\(n+1\) 个数中必有两个互质」	相邻数对
「循环节长度有上界」	状态数有限（如斐波那契模 \(p\)，见 85 章）

「必存在一段连续和被 \(n\) 整除」的证明值得记住： 考虑 \(n+1\) 个前缀和 \(S_0=0, S_1, \ldots, S_n\) 模 \(n\) 的余数， 只有 \(n\) 种取值，必有 \(S_i\equiv S_j\)（\(i<j\)），则 \(a_{i+1}+\cdots+a_j\) 被 \(n\) 整除。\(\square\)

---

84.7　容斥原理

loriex 的课件从最简单的形式讲起：

\(|A\cup B| = |A| + |B| - |A\cap B|\)

一般形式：

\[\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i\cap A_j| + \cdots + (-1)^{n-1}\left|\bigcap_{i=1}^{n}A_i\right|\]

即 \(\sum_{\emptyset \ne S \subseteq [n]}(-1)^{|S|+1}\left|\bigcap_{i\in S}A_i\right|\)。

补集形式更常用（「正难则反」）：

\[\left|\overline{\bigcup A_i}\right| = \sum_{S\subseteq[n]}(-1)^{|S|}\left|\bigcap_{i\in S}A_i\right|\]

课件的例题：「求 \(1..n\) 中有多少个数是 2 的倍数或 3 的倍数」， 答案 \(\lfloor n/2\rfloor+\lfloor n/3\rfloor-\lfloor n/6\rfloor\)。

loriex 还提醒了一句实话： 「这个常常和数论的乱七八糟的东西混到一起，结果是难度的骤升。」 莫比乌斯函数本质上就是容斥的系数——见 83 章。

实现：\(n\le20\) 时直接枚举 \(2^n\) 个子集（用位运算，见 46-位运算）：

# [片段] 模板：容斥，枚举 n <= 20 个条件的子集
def inclusion_exclusion(n, size_of_intersection):
    """size_of_intersection(mask) 返回 mask 中所有条件同时成立的元素个数。
    返回「至少满足一个条件」的元素个数。"""
    total = 0
    # mask 从 1 开始：空集对应「不加任何限制」，容斥的一般形式里不含这一项
    for mask in range(1, 1 << n):
        # 容斥系数 (-1)^(|S|+1)：奇数个条件取 +1、偶数个取 -1。
        # bin(mask).count("1") 就是 |S|，在 C 层数 1 的个数比逐位移位快
        sign = -1 if bin(mask).count("1") % 2 == 0 else 1
        total += sign * size_of_intersection(mask)
    return total

---

84.8　卡特兰数

loriex 的课件用括号序列引入：

\(n\) 个 {} 杂乱地排成一串，问有多少种排法使得每个前缀中 { 的数目不少于 } 的数目。

设 \(C_n\) 为答案。枚举「第一个 { 匹配的 } 之间有多少个括号对」：

\[C_n = \sum_{i=0}^{n-1} C_i\, C_{n-1-i}, \qquad C_0 = 1\]

这就是卡特兰数：\(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \ldots\)

课件的经验之谈：「如果你打表看到这样的数列，兴许就是 Catalan 数。」

通项公式

\[C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n}-\binom{2n}{n-1}\]

证明（反射法）：把 { 看成 \(+1\)、} 看成 \(-1\)， 总方案 \(\binom{2n}n\) 中要减掉「某个前缀和变成 \(-1\)」的坏方案。 对每个坏方案，取第一次到达 \(-1\) 的位置，把该位置之前的所有步取反， 得到一个从 \(-2\) 走到 \(0\)（即含 \(n+1\) 个 \(+1\)、\(n-1\) 个 \(-1\)）的序列， 这是双射。所以坏方案数是 \(\binom{2n}{n-1}\)，作差即得。\(\square\)

递推形式（实战最好用）

\[C_n = C_{n-1}\cdot\frac{2(2n-1)}{n+1}\]

模意义下用逆元实现。

等价模型（考点全在这里）

模型	答案
\(n\) 对括号的合法序列	\(C_n\)
\(1..n\) 依次入栈，合法出栈序列数	\(C_n\)
从 \((0,0)\) 走到 \((n,n)\)，只向右/向上，不越过对角线	\(C_n\)
\(n\) 个节点的不同二叉树形态数	\(C_n\)
凸 \(n\) 边形用不交对角线剖成三角形	\(C_{n-2}\)
\(n+1\) 个数的加括号方式	\(C_n\)

（loriex 课件的第 40、42 页正是格路径模型和凸多边形剖分模型。）

# [片段] 模板：卡特兰数前 n 项（模 P，P 为质数）
def catalan(n, P):
    """返回 [C_0, C_1, ..., C_n]。用递推 C_n = C_{n-1} * 2(2n-1) / (n+1)。"""
    res = [1] * (n + 1)                  # C_0 = 1，其余会被下面覆盖
    for i in range(1, n + 1):
        # 模意义下的「除以 i+1」= 乘 i+1 的逆元；P 是质数，用费马小定理求。
        # 每两次乘法之间就取一次模，中间量始终小于 P²
        res[i] = res[i - 1] * 2 % P * (2 * i - 1) % P * pow(i + 1, P - 2, P) % P
    return res

\(n\) 大时把 pow(i+1, P-2, P) 换成预处理的逆元表（81 章 模板）， 否则 \(n\) 次模幂会成为瓶颈。

---

84.9　错位排列

问题：\(n\) 封信装进 \(n\) 个信封，每封信都装错的方案数 \(D_n\)（也叫「重排列」「derangement」）。

\[D_1 = 0,\quad D_2 = 1,\quad D_n = (n-1)(D_{n-1}+D_{n-2})\]

递推的证明：考虑元素 1 放到了位置 \(k\)（有 \(n-1\) 种选择）。 - 若元素 \(k\) 恰好放到位置 1，剩下 \(n-2\) 个元素构成 \(D_{n-2}\)； - 否则把「元素 \(k\) 不能放位置 1」看成「元素 \(k\) 不能放它自己的位置」， 剩下 \(n-1\) 个元素构成一个 \(D_{n-1}\)。

所以 \(D_n=(n-1)(D_{n-1}+D_{n-2})\)。\(\square\)

容斥形式：设 \(A_i\) 是「第 \(i\) 封信装对」的方案集合，\(|A_S| = (n-|S|)!\)，

\[D_n = \sum_{k=0}^{n}(-1)^k\binom nk (n-k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}\]

由 \(e^{-1}=\sum(-1)^k/k!\) 得 \(D_n \approx n!/e\)，实际上

\[D_n = \left\lfloor \frac{n!}{e} + \frac12 \right\rfloor \quad (n\ge1)\]

前几项：\(0, 1, 2, 9, 44, 265, 1854\)。

# [片段] 模板：错位排列前 n 项（模 P）
def derangement(n, P):
    # 表长取 max(n, 2)：n = 0 或 1 时也要留出 D[0]、D[1] 两个初值的位置
    D = [0] * (max(n, 2) + 1)
    D[0] = 1                             # 空排列只有一种，且是「全部装错」的
    D[1] = 0                             # 唯一的一封信只能装对，没有错排
    for i in range(2, n + 1):
        # 元素 1 放到位置 k（i-1 种选法）；k 回放位置 1 则剩 D[i-2]，否则剩 D[i-1]
        D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % P
    return D

推广（部分错位）：恰有 \(k\) 个位置对的方案数 \(=\binom nk D_{n-k}\)。

---

84.10　斯特林数与贝尔数

Colin 的《NOIP 组合数学、数论选讲》把这三个列在一起，因为它们都在回答「划分」问题。

第二类斯特林数 \(S(n,k)\)

定义：把 \(n\) 个不同的球放进 \(k\) 个相同的盒子，每盒非空的方案数。 记作 \(S(n,k)\) 或 \(\begin{Bmatrix}n\\k\end{Bmatrix}\)。

\[S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\]

证明：看第 \(n\) 个球。 - 它单独占一个盒子：剩下 \(n-1\) 个球分成 \(k-1\) 个非空盒，\(S(n-1,k-1)\)； - 它加入已有的盒子：先把前 \(n-1\) 个球分成 \(k\) 个非空盒（\(S(n-1,k)\)）， 再选一个盒子放进去（\(k\) 种）。\(\square\)

边界：\(S(0,0)=1\)，\(S(n,0)=0\ (n\ge1)\)，\(S(n,n)=1\)，\(S(n,1)=1\ (n\ge1)\)。

通项（容斥）：

\[S(n,k) = \frac{1}{k!}\sum_{i=0}^{k}(-1)^i\binom ki (k-i)^n\]

推导：先算「\(n\) 个不同球放进 \(k\) 个不同盒子且每盒非空」的方案数—— 由容斥，\(\sum_i(-1)^i\binom ki(k-i)^n\)（减去至少空 1 个盒的情形）。 盒子变成相同的，除以 \(k!\)。\(\square\)

相关公式（「幂转下降幂」）：\(x^n = \sum_{k=0}^{n} S(n,k)\, x^{\underline k}\)， 其中 \(x^{\underline k}=x(x-1)\cdots(x-k+1)\)。这是自然数幂和类题目的常用武器。

第一类斯特林数 \(s(n,k)\)

定义（无符号）：把 \(n\) 个不同元素排成 \(k\) 个非空圆排列（轮换）的方案数。

\[c(n,k) = c(n-1,k-1) + (n-1)\,c(n-1,k)\]

证明：第 \(n\) 个元素要么自成一个轮换（\(c(n-1,k-1)\)）， 要么插入已有轮换里某个元素的右边（前 \(n-1\) 个元素各有一个位置，共 \(n-1\) 种）。\(\square\)

关系：\(\sum_k c(n,k) = n!\)（每个排列唯一分解成若干轮换）， 以及 \(x^{\overline n}=\sum_k c(n,k)x^k\)（上升幂展开）。

贝尔数 \(B_n\)

定义：\(n\) 个元素的集合的全部划分数（不限盒子数）。

\[B_n = \sum_{k=0}^{n} S(n,k), \qquad B_{n+1} = \sum_{k=0}^{n}\binom nk B_k\]

第二个递推的证明：看元素 \(n+1\) 所在的块。设该块除自己外还有 \(k\) 个元素， 从其余 \(n\) 个里选（\(\binom nk\) 种），剩下 \(n-k\) 个任意划分（\(B_{n-k}\)）。 求和并把 \(k\) 换成 \(n-k\) 即得。\(\square\)

前几项：\(B_0=1,\ 1,\ 2,\ 5,\ 15,\ 52,\ 203,\ 877\)。

# [片段] 模板：第二类斯特林数表、第一类斯特林数表、贝尔数
def stirling2(n, P):
    """S[i][j]，O(n²)。n <= 2000 在 Python 下才实用。"""
    S = [[0] * (n + 1) for _ in range(n + 1)]
    S[0][0] = 1                          # 0 个球分成 0 个非空盒：唯一的空划分
    for i in range(1, n + 1):
        for j in range(1, i + 1):        # j > i 时无法每盒非空，保持 0
            # 第 i 个球：塞进已有的 j 个盒之一（j 种），或自己独占一盒
            S[i][j] = (j * S[i - 1][j] + S[i - 1][j - 1]) % P
    return S


def stirling1(n, P):
    """无符号第一类斯特林数 c[i][j]（轮换数），O(n²)。"""
    c = [[0] * (n + 1) for _ in range(n + 1)]
    c[0][0] = 1                          # 空集恰好排成 0 个轮换
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            # 第 i 个元素：自成一个新轮换，或插到前 i-1 个元素中某一个的右边
            c[i][j] = (c[i - 1][j - 1] + (i - 1) * c[i - 1][j]) % P
    return c


def bell(n, P, C):
    """贝尔数 B_0..B_n，用 B_{k+1} = Σ C(k,j) B_j。C 是组合数函数。"""
    B = [0] * (n + 1)
    B[0] = 1                             # 空集只有一种划分（不含任何块）
    for k in range(n):
        s = 0
        # 看元素 k+1 所在的块：从其余 k 个里挑出 j 个「不跟它同块」的元素
        # （C(k,j) 种），这 j 个再任意划分（B[j] 种），其余的全部并入它的块
        for j in range(k + 1):
            s += C(k, j) * B[j] % P      # 内层不取模，靠 Python 大整数扛住再统一模
        B[k + 1] = s % P
    return B

四类计数问题的对照表（球放盒子的经典四分法）：

球	盒	每盒非空	方案数
不同	不同	否	\(k^n\)
不同	不同	是	\(k!\,S(n,k)\)
不同	相同	是	\(S(n,k)\)
不同	相同	否	\(\sum_{i\le k}S(n,i)\)（\(k\ge n\) 时为 \(B_n\)）
相同	不同	是	\(\binom{n-1}{k-1}\)（隔板法）
相同	不同	否	\(\binom{n+k-1}{k-1}\)
相同	相同	—	整数拆分，需 DP

---

84.11　例题

BISHI67 穿搭大挑战（简单）

\(T \le 10^3\) 组，每组给上衣 \(a\)、裤子 \(b\)、鞋 \(c\)（各 \(\le 10^9\)）。 每天恰好忘穿一种，求不同穿搭方案数（不取模）。 题面见 BISHI67 原题（牛客）。

加法原理 + 乘法原理的最朴素应用。「忘穿一种」意味着恰好穿剩下两类各一件，三种互斥情形：

情形	方案数
忘穿上衣	\(bc\)
忘穿裤子	\(ac\)
忘穿鞋	\(ab\)

答案 \(= ab+bc+ca\)。三类不会重复（缺的那一类不同，穿搭本身就不同）。

验算样例：\(a=2,b=1,c=2 \to 2\times1+1\times2+2\times2 = 2+2+4 = 8\) ✓

import sys


def main():
    data = sys.stdin.buffer.read().split()   # 整块读入，T 到 1e3 时逐行读会被 IO 拖慢
    t = int(data[0])
    out = []
    for i in range(t):
        # 第 i 组的三个数紧挨在一起，下标偏移 1 是跳过开头的 t
        a = int(data[1 + 3 * i]); b = int(data[2 + 3 * i]); c = int(data[3 + 3 * i])
        # 三种「忘穿哪一类」互斥，加法原理；每种内部是两类各选一件，乘法原理。
        # 题面没有模数，Python 大整数直接给精确值（答案可达 3e18）
        out.append(str(a * b + b * c + c * a))
    sys.stdout.write("\n".join(out) + "\n")  # 攒够一次性输出


main()

三个坑：

1. 题目没说取模，别自作主张 mod \(10^9+7\)；
2. 别理解成「至多忘穿一种」（那还要加上 \(abc\)）——样例 8 明确排除了全穿的 4 种；
3. 答案最大 \(3\times10^{18}\)，贴着 int64 上界 \(9.22\times10^{18}\)。 C++ 选手要小心（换成 \(a,b,c\le2\times10^9\) 就溢出了），Python 无限精度，不用管。

题解见 solutions/BISHI67.py。

BISHI69 [HNOI2008] 越狱（简单）

\(N \le 10^{12}\) 个房间排成一排，每人信仰 \(M \le 10^8\) 种宗教之一。 若存在相邻两人信仰相同则「可能越狱」。求可能越狱的方案数，模 \(P=100003\)。 题面见 BISHI69 原题（牛客）。

正难则反——直接数「存在相邻相同」很难，数它的反面很容易：

量	方案数
总方案	\(M^N\)
不会越狱（任意相邻都不同）	\(M(M-1)^{N-1}\)
答案	\(M^N - M(M-1)^{N-1}\)

（不越狱的方案：第 1 间任选 \(M\) 种，之后每间只要和前一间不同，各 \(M-1\) 种——乘法原理。）

验算样例：\(M=2, N=3 \to 2^3 - 2\times1^2 = 8-2 = 6\) ✓ \(N=1\) 时：\(M - M(M-1)^0 = 0\)，符合直觉（只有一间房谈不上相邻）。

import sys

P = 100003

m, n = map(int, sys.stdin.buffer.read().split()[:2])
# 底数先 % P 再进 pow：M 可达 1e8，指数 N 可达 1e12，内置 pow 是 C 层模幂，
# 约 40 次平方就出结果，不需要（也不能）用费马小定理把指数降到 N mod (P-1)
total = pow(m % P, n, P)                       # M^N
safe = m % P * pow((m - 1) % P, n - 1, P) % P  # M*(M-1)^(N-1)：任意相邻都不同
# 正难则反：总方案减去「一定不会越狱」的方案。差可能为负，靠 % P 拉回 [0, P)
sys.stdout.write(str((total - safe) % P) + "\n")

四个坑：

1. 不能用费马小定理把指数降到 \(N \bmod (P-1)\)！ \(M\) 可能是 \(P=100003\) 的倍数（\(M\le10^8\) 完全够大），此时 \(M\equiv0\pmod P\)， 费马小定理的前提 \(\gcd(M,P)=1\) 不成立，降幂会算错。 直接 pow(m % P, n, P) 就好——\(\log_2 10^{12}\approx40\) 层，根本不需要降；
2. 相减可能得负数，最后统一 % P 转正（Python 自动给非负）；
3. \(M=1\) 时 \((M-1)=0\)：\(N=1\) 时 pow(0,0,P)==1，答案 \(1-1=0\)； \(N\ge2\) 时 pow(0,N-1,P)==0，答案 \(1-0=1\)。都正确；
4. \(N\) 到 \(10^{12}\) 超过 int32。

模数 \(P=100003\) 是质数但很小——这类题最容易被「顺手用费马小定理降幂」坑到。 降幂的前提永远是底数与模数互质，见 82-欧拉函数与欧拉降幂。

题解见 solutions/BISHI69.py。

BISHI70 【模板】组合数（中等）

\(T \le 10^5\) 组，每组给 \(0 \le n \le m \le 5\times10^5\)，求 \(\binom mn \bmod (10^9+7)\)。 题面见 BISHI70 原题（牛客）。

标准的阶乘表 + 阶乘逆元倒推。

做法	复杂度	判断
每次现算 \(O(n)\) 连乘	\(10^5\times5\times10^5 = 5\times10^{10}\)	❌
每个阶乘逆元都 pow(fact[i], P-2, P)	\(5\times10^5\) 次模幂	⚠️ 浪费
阶乘表 + 逆元倒推	\(O(\max m + T)\)，1 次模幂	✅

\(P=10^9+7\) 是质数且 \(P > 5\times10^5\)，所以 \(1..\max m\) 都与 \(P\) 互质， 逆元全部存在，不需要 Lucas（那是 \(m\) 超过模数时才要的）。

import sys

P = 1000000007


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    # 每组两个数，隔项切片一次取出全部 n 与全部 m，切片在 C 层完成
    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                   # 表长按实际最大的 m 定，不用盲开 5e5

    # 阶乘表：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
    for n, m in zip(ns, ms):
        # 题面的 C(m, n) 是「从 m 个里选 n 个」，所以上标是 m、下标是 n。
        # 题面已保证 0 <= n <= m，m - n 不会变负，无需额外判边界
        ap(str(fact[m] * inv_fact[n] % P * inv_fact[m - n] % P))
    sys.stdout.write("\n".join(out) + "\n")


main()

四个坑：

1. 题面写的是 \(C_m^n\)，即「从 \(m\) 个里选 \(n\) 个」，\(n\) 是下标、\(m\) 是上标，别读反。 样例 2 4 给的是 \(n=2, m=4\)，答案 \(\binom42=6\)；
2. 边界 \(n=0\) 或 \(n=m\) 时答案 1，fact[0]=1 已经覆盖；
3. 先把全部询问读进来求 \(\max m\)，再决定表长——大部分测试点的 \(m\) 远小于上限， 能省掉大量预处理时间（样例里最大只有 5）；
4. \(T\) 到 \(10^5\)，缓冲 IO 必需。

切片取隔项的技巧：data[1:1+2*t:2] 直接取出所有 \(n\)， data[2:2+2*t:2] 取出所有 \(m\)，比写循环快——切片在 C 层完成。

题解见 solutions/BISHI70.py。

BISHI71 人员分组问题（中等）

从 \(n \le 10^6\) 人中选出恰好 5～7 人的小组，求方案数模 \(10^9+7\)。 题面见 BISHI71 原题（牛客）。

「恰好 5～7 人」是三种互斥情形，加法原理：

\[\text{答案} = \binom n5 + \binom n6 + \binom n7\]

关键取舍：下标固定只有 5、6、7 三个，完全不必预处理 \(10^6\) 的阶乘表。 用下降阶乘 \(O(1)\) 算就行——比建表还快，内存也是 \(O(1)\)。

import sys

P = 1000000007


def comb(n, k):
    """C(n,k) mod P，k 很小时的 O(k) 写法；n < k 时返回 0。"""
    if n < k:
        return 0                        # 人不够组不成队，方案数为 0
    # 分子：下降阶乘 n(n-1)...(n-k+1)，恰好 k 项
    num = 1
    for i in range(k):
        num = num * (n - i) % P         # 每项即时取模，n 到 1e6 也不膨胀
    # 分母：k! 只有 120 / 720 / 5040，精确算即可
    den = 1
    for i in range(1, k + 1):
        den *= i
    return num * pow(den, -1, P) % P     # Python 3.8+：负指数 = 扩展欧几里得求逆元


n = int(sys.stdin.buffer.read().split()[0])
# 「恰好 5 / 6 / 7 人」是三种互斥情形，加法原理直接相加。
# 下标只有三个固定值，用 O(k) 的下降阶乘比预处理 1e6 的阶乘表更省
sys.stdout.write(str((comb(n, 5) + comb(n, 6) + comb(n, 7)) % P) + "\n")

三个坑：

1. \(n<5\) 时答案为 0（样例 \(n=1\) 就是 0）；\(n=5\) 或 6 时只有前一两项非零。 comb() 里必须先判 n < k 直接返回 0——否则下降阶乘会算出 \(6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot0\) 这种带 0 的乘积（结果碰巧也是 0）， 甚至出现负因子；虽然模意义下仍正确，但显式判掉更清楚；
2. 分母 \(k!\in\{120,720,5040\}\) 都远小于 \(P\) 且与 \(P\) 互质， pow(den, -1, P) 和 pow(den, P-2, P) 等价；
3. 最终和要再取一次模。

能不能用 math.comb(n, 5)？ 能。\(n=10^6\)、\(k=7\) 时分子只有 42 位， math.comb 秒出，再 % P 即可。但模意义下的写法才是这类题的通用姿势—— 一旦 \(k\) 变成 \(n/2\)，math.comb 就废了。

题解见 solutions/BISHI71.py。

BISHI66 子数列求积（中等）

\(n, q \le 10^5\)，序列 \(1\le a_i < 10^9+7\)。\(q\) 次询问区间乘积 \(\prod_{i=l}^{r}a_i \bmod (10^9+7)\)， 输出一行 \(q\) 个数、空格分隔。 题面见 BISHI66 原题（牛客）。

说明：大纲把这题排在组合数学章，但它真正的考点是 81-快速幂与逆元 的批量求逆。 放在这里正好当作「逆元 → 组合数」的过渡：组合数的 \(\frac{n!}{m!(n-m)!}\) 用的就是同一套「前缀积 + 逆元」的思想。

前缀和的乘法版：

\[\prod_{i=l}^{r}a_i = \operatorname{pre}[r]\cdot \operatorname{pre}[l-1]^{-1} \pmod P\]

能这么做的前提是每个 \(a_i\) 在模 \(P\) 下可逆。这里 \(1\le a_i < P\) 且 \(P\) 是质数， 所以 \(a_i\bmod P\ne0\)，前缀积恒不为 0，逆元必然存在。

逆元用批量求逆：只对 \(\operatorname{pre}[n]\) 做一次 pow，然后倒推 \(\operatorname{ipre}[i-1]=\operatorname{ipre}[i]\cdot a_i\)。总共 \(O(n+q)\)，只有 1 次模幂。

import sys

P = 1000000007


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); q = int(data[1])
    a = [int(x) % P for x in data[2:2 + n]]  # 读入即取模，后面的乘法都是小整数

    # 前缀积：pre[i] = a[0]*...*a[i-1]，pre[0] = 1 是乘法单位元
    pre = [1] * (n + 1)
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] * a[i - 1] % P

    ipre = [1] * (n + 1)                     # 批量求逆：只做一次模幂
    ipre[n] = pow(pre[n], P - 2, P)          # 只对最后一个前缀积求逆
    for i in range(n, 0, -1):
        # 1/(a0..a_{i-2}) = 1/(a0..a_{i-1}) * a_{i-1}，倒着乘回去即可
        ipre[i - 1] = ipre[i] * a[i - 1] % P

    out = []
    ap = out.append
    base = 2 + n                             # 询问从数组之后开始，每个询问占两项
    for j in range(q):
        l = int(data[base + 2 * j]); r = int(data[base + 2 * j + 1])
        # 询问是 1-indexed 闭区间：pre[r] 含 a[0..r-1]，除掉 a[0..l-2] 即得 [l, r]
        ap(str(pre[r] * ipre[l - 1] % P))
    sys.stdout.write(" ".join(out) + "\n")   # ★ 一行输出，空格分隔


main()

四个坑：

1. 询问是 1-indexed 闭区间 \([l,r]\)，对应 pre[r] * ipre[l-1]；
2. 输出要求是一行 \(q\) 个数用空格分隔，不是每行一个——读题时容易漏；
3. 逐次 pow(pre[l-1], P-2, P) 也能过（\(10^5\) 次 C 层模幂约 0.15 秒）， 但批量求逆是标准做法，只有 1 次模幂；
4. IO 量约 \(3\times10^5\) 个整数，必须 buffer.read().split()。

如果 \(a_i\) 可能是 \(P\) 的倍数怎么办？（本题不会，但这是常见变形） 前缀积会变成 0，逆元不存在。标准技巧是记录 0 的个数 + 只对非零部分做前缀积： 若 \([l,r]\) 内有 0 则答案为 0，否则用非零前缀积相除。

题解见 solutions/BISHI66.py。

---

84.12　本章速查

公式表

名称	公式
排列数	\(A_n^m = \dfrac{n!}{(n-m)!}\)
组合数	\(\binom nm = \dfrac{n!}{m!(n-m)!}\)
杨辉恒等式	\(\binom nm=\binom{n-1}{m-1}+\binom{n-1}m\)
二项式定理	\((a+b)^n=\sum_k\binom nk a^{n-k}b^k\)
范德蒙德卷积	\(\sum_k\binom mk\binom n{r-k}=\binom{m+n}r\)
曲棍球恒等式	\(\sum_{i=r}^n\binom ir=\binom{n+1}{r+1}\)
Lucas	\(\binom nm\equiv\prod\binom{n_i}{m_i}\pmod p\)
隔板法（非空）	\(\binom{n-1}{k-1}\)
隔板法（可空）	\(\binom{n+k-1}{k-1}\)
容斥	$\left
卡特兰数	\(C_n=\frac1{n+1}\binom{2n}n=\binom{2n}n-\binom{2n}{n-1}\)
卡特兰递推	\(C_n=C_{n-1}\cdot\frac{2(2n-1)}{n+1}\)
错位排列	\(D_n=(n-1)(D_{n-1}+D_{n-2})=\lfloor n!/e+1/2\rfloor\)
第二类斯特林	\(S(n,k)=kS(n-1,k)+S(n-1,k-1)\)
第一类斯特林	\(c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)\)
贝尔数	\(B_{n+1}=\sum_k\binom nk B_k\)

组合数取模：选型表

条件	做法
\(n\le2000\)，模数任意（含合数）	杨辉三角 \(O(n^2)\)
\(n\le5\times10^5\)，\(P\) 质数且 \(P>n\)，多次询问	阶乘表 + 逆元倒推
\(k\) 很小（\(\le100\)），\(n\) 很大	下降阶乘 + 一次求逆
\(n,m\) 到 \(10^{18}\)，\(P\) 质数且小	Lucas
\(P=p^k\) 或一般合数	扩展 Lucas + CRT
要精确值且 \(\min(k,n-k)\) 小	math.comb（3.8+）

Python 取舍

场景	做法	理由
阶乘逆元	倒推，只做 1 次 pow	\(n\) 次模幂太浪费
组合数 C(a,b)	先判 b<0 or b>a: return 0	兜住全部边界
取隔项参数	切片 data[1:1+2*t:2]	C 层完成
表长	先读完询问取 \(\max\)	大部分点远小于上限
精确组合数	math.comb / math.perm	C 实现
取模 + \(k\) 大	绝不用 math.comb	中间大整数十几万位
杨辉三角	\(n\le2000\)	\(O(n^2)\) 纯 Python 循环
斯特林数表	\(n\le2000\)	同上

看到什么 → 想到什么

题面特征	第一反应
「或者 / 分类」	加法原理（检查互斥！）
「并且 / 分步」	乘法原理（检查独立！）
「至少存在一个……」	正难则反：总数 − 反面（BISHI69）
「恰好 \(k\) 个」且 \(k\) 有几种取值	分别算再相加（BISHI71）
「相邻必须在一起」	捆绑法
「相邻不能在一起」	插空法 / 正难则反
「相同物品分组」「不定方程解数」	隔板法
「至少两个……」「必然存在」	鸽巢原理
「不重不漏地数并集」	容斥
打表得到 1,1,2,5,14,42	卡特兰数
括号 / 出栈序列 / 二叉树形态 / 不越对角线	卡特兰数
「全部装错」	错位排列
「划分成若干非空组」	第二类斯特林数 / 贝尔数
「排成若干个环」	第一类斯特林数
区间乘积 + 取模	前缀积 + 批量求逆（BISHI66）