---

数学背景：

《命题人讲座 集合与对应》P25 容斥原理

你好！很高兴能以数学竞赛教练的身份和你探讨这个问题。

这张图片里的内容非常有代表性，它展示了组合数学中一个核心的大杀器——容斥原理（Inclusion-Exclusion Principle），教材里生动地称之为 “逐步淘汰原则”。

很多同学背公式 $|I| - \sum |A_i| + \sum |A_i \cap A_j| - \dots$ 觉得很痛苦。今天咱们不背死公式，我带你用“筛沙子”的直觉来把这个道理彻底搞通。

---

🏆 教练的启发式讲解

1. 设定场景：为什么我们需要“淘汰法”？

看例题3：9个人进4个车厢，每个车厢都不能空。

如果正面硬攻，你要考虑：

• 是 6+1+1+1 的队形？
• 还是 3+2+2+2 的队形？
• 还是 5+2+1+1？ 情况太多了，分类讨论会累死人，而且容易漏。

教练心法： 当“正面进攻”这就好比你要从一堆混杂的豆子里挑出几颗金豆子，很难挑；不如反过来想——我们把所有的豆子都拿来，把“坏豆子”扔掉，剩下的不就是金豆子了吗？

这就是正难则反 逐步淘汰的核心思想。

2. 第一轮淘汰：简单粗暴（但也带来了漏洞）

我们定义全集 $I$：9个人随便进4个车厢，不管空不空。

$$|I| = 4^9$$

但是，我们的目标是“没有空车厢”。 那么，“坏人”是谁？是那些至少有一个车厢空着的情况。

好，我们开始淘汰（做减法）：

• 减去 第1个车厢空的情况；
• 减去 第2个车厢空的情况；
• ...
• 减去 第4个车厢空的情况。

这一步我们减去了 $C_4^1 \times 3^9$（选1个车厢让它空，剩下3个车厢随便装）。

🛑 停！这里有个巨大的漏洞！

大家想一想：假如有一种情况是“1号和2号车厢同时空着”。

• 当你减去“1号空”的时候，你把这种情况扔了一次。
• 当你减去“2号空”的时候，你又把这种情况扔了一次。

结论： 我们减多了！把同时空两个的情况多减了一次，必须加回来。

3. 第二轮修正：由于“冤杀”，必须补偿

为了弥补刚才多减的过错，我们需要把那些**“同时空2个车厢”**的情况加回来。

• 任选2个车厢空：$C_4^2$
• 剩下2个车厢随便装：$2^9$

所以，我们加上 $+ C_4^2 \times 2^9$。

🛑 停！还没完！

大家再想深一层：假如有一种情况是“1号、2号、3号车厢同时空着”。 让我们算算它经历了什么：

1. 在第一轮（减1个空）时，它被减了3次（因为1空、2空、3空都包含它）。 (-3)
2. 在第二轮（加2个空）时，它被加了3次（因为1&2空、1&3空、2&3空都包含它）。 (+3)

$-3 + 3 = 0$。 哎？这意味着这种“坏情况”虽然被折腾来折腾去，最后居然没有被淘汰掉（净计数为0），它还混在我们的队伍里！

结论： 必须把它再减出去！

4. 第三轮修正：继续淘汰

我们要减去**“同时空3个车厢”**的情况。

• 任选3个车厢空：$C_4^3$
• 剩下1个车厢随便装：$1^9$

所以，我们减去 $- C_4^3 \times 1^9$。

5. 终极检查

那如果是“4个车厢都空”呢？（虽然本题 $4^0$ 不可能，但在逻辑上要闭环）。 它被：

• 减了 $C_4^1$ 次（4次）
• 加了 $C_4^2$ 次（6次）
• 减了 $C_4^3$ 次（4次）
• $-4 + 6 - 4 = -2$。 我们需要它最终贡献为0（因为它也是坏情况，应该被排除，但之前的总和公式通常包含在最后一项里，或者如果是求有效部分，它应该被减掉1次）。但在本题中，4个都空意味着没人进去，这在 $1^9$ 中其实已经处理到了极限（只剩1个车厢有人）。

在本题公式中，最后加上 $C_4^4 \times 0$ 是为了形式完整，逻辑上到上面一步就已经把所有杂质筛干净了。

---

🎯 总结：“逐步淘汰”的节奏感

你看，这个过程就像一个摆钟，左右摇摆，幅度越来越小：

1. 全拿来（$4^9$）
2. 减多了（减去有一个空的，$- C_4^1 3^9$）
3. 加多了（补回有两个空的，$+ C_4^2 2^9$）
4. 又减多了（减去有三个空的，$- C_4^3 1^9$）
5. ...直到无法再分。

这就是图片中公式 $(5)$ 的含义：

$$\text{答案} = \sum_{k=0}^{n} (-1)^k C_n^k (n-k)^m$$

• 符号：一正一负，代表“减多了加回来，加多了再减去”。
• $C_n^k$：代表这一轮我们关注的是“k个坏蛋”的组合。
• $(n-k)^m$：代表剩下的自由空间。

🧠 教练的最后点拨

以后做题，只要看到：

1. “至少”、“全部不” 这样的字眼；
2. 或者像本题这种**“满射”**问题（球要把盒子占满，不能空）；

你的脑海里就要立刻浮现出这个**“左右横跳”**的画面。

记忆口诀：

总数起头做减法， 单个属性轮流杀。 交集减多要补回， 三个重叠再减它。 奇减偶加直到尾， 逐步淘汰得精华。

希望这个讲解能让你看到这一长串枯燥公式背后，其实是一个非常严谨且自然的逻辑修补过程！加油！

---

这是一个非常适合改编成编程题的数学场景。在信息学奥赛（OI）体系中，这类问题属于 组合数学 与 动态规划（DP） 或 深度优先搜索（DFS） 的结合。

针对GESP 4~5级（大致对应小学高年级到初中刚入门算法的水平），我们不需要学生推导复杂的容斥公式，而是侧重于考察递归搜索或者基础的递推/DP能力。

以下是改编后的题目文档：

---

[GESP 5级] 列车调度员 (Passenger Allocation)

题目描述

火车站来了 $N$ 名乘客，都在排队准备上车。现在的列车一共有 $M$ 个车厢（车厢编号为 $1$ 到 $M$）。 为了保证列车的平衡运行，调度员有一个严格的要求：每个车厢都至少要有一名乘客，不能有空车厢。

假设 $N$ 名乘客是不同的（有不同的名字），$M$ 个车厢也是不同的（有不同的编号）。 请问一共有多少种不同的分配方案？

例如：有 3 名乘客进 2 个车厢。 方案包括：

1. (1,2)号乘客进1号车厢，(3)号乘客进2号车厢
2. (1,3)号乘客进1号车厢，(2)号乘客进2号车厢
3. (2,3)号乘客进1号车厢，(1)号乘客进2号车厢
4. (3)号乘客进1号车厢，(1,2)号乘客进2号车厢
5. (2)号乘客进1号车厢，(1,3)号乘客进2号车厢
6. (1)号乘客进1号车厢，(2,3)号乘客进2号车厢 共 6 种。

输入格式

输入一行，包含两个正整数 $N$ 和 $M$，用空格隔开。 含义如题所述：$N$ 为乘客数量，$M$ 为车厢数量。

输出格式

输出一个整数，表示满足条件的分配方案总数。

样例 #1

样例输入 #1

3 2

样例输出 #1

6

样例 #2

样例输入 #2

9 4

样例输出 #2

186480

数据范围

• 对于 $100\%$ 的数据，保证 $1 \le M \le N \le 10$。
• 题目保证最终答案在 64 位整数范围（long long）内。

---

💡 题目解析与思路提示（教练版）

这道题对于 GESP 5 级的学生来说，是考察 递归（DFS） 或者 基础动态规划（DP） 的绝佳题目。虽然可以用数学公式（容斥原理）秒杀，但编程考级更看重算法实现能力。

思路一：深度优先搜索 (DFS) —— 最直观

由于数据范围 $N \le 10$，数据量很小，我们可以模拟每一个乘客的选择。

1. 定义状态：dfs(passenger_id, count_of_occupied_carriages)
   • 当前正在安排第几位乘客？
   • 当前已经有多少个车厢是非空的？（或者记录每个车厢的人数）
2. 递归过程：
   • 第 i 个乘客可以走进 $1$ 到 $M$ 号任意一个车厢。
   • 如果他走进的是一个空车厢，那么非空车厢数量 $+1$。
3. 边界条件（递归出口）：
   • 当 $N$ 个乘客都安排完了。
   • 检查：非空车厢的数量是否正好等于 $M$？如果是，这就 1 种合法方案，返回 1；否则返回 0。
4. 剪枝优化：
   • 如果剩下的乘客全部分配到新车厢，也无法填满 $M$ 个车厢，可以提前停止搜索（可行性剪枝）。

思路二：动态规划 (DP) —— 进阶解法（第二类斯特林数）

我们可以换个角度思考：这是典型的将 $N$ 个不同的小球放入 $M$ 个不同的盒子，且盒子不空的问题。

• 状态定义：设 $dp[i][j]$ 表示将 $i$ 个人放入 $j$ 个车厢（车厢无区别）且无空车厢的方法数。
• 状态转移：当我们考虑第 $i$ 个人时：
  1. 独自占一个新车厢：前 $i-1$ 个人已经占了 $j-1$ 个车厢，第 $i$ 个人开辟第 $j$ 个车厢。
     • 方案数：$dp[i-1][j-1]$
  2. 挤进已有的车厢：前 $i-1$ 个人已经占了 $j$ 个车厢，第 $i$ 个人可以从这 $j$ 个车厢里随便选一个进。
     • 方案数：$dp[i-1][j] \times j$
  • 转移方程：$dp[i][j] = dp[i-1][j-1] + j \times dp[i-1][j]$
  • 注：这就是著名的“第二类斯特林数”递推公式。(见《命题人讲座 集合与对应P98》
• 最终答案：因为题目中车厢是有编号的（不同的），所以最后要乘上车厢的排列数 $M!$。
  • $Answer = dp[N][M] \times M!$

参考代码结构 (C++)

#include <iostream>
using namespace std;

int N, M;
long long ans = 0;
int box[15]; // 记录每个车厢的人数

// DFS解法
void dfs(int p) {
    // 边界：所有人都上车了
    if (p > N) {
        int occupied = 0;
        for (int i = 1; i <= M; i++) {
            if (box[i] > 0) occupied++;
        }
        if (occupied == M) ans++;
        return;
    }

    // 剪枝：如果剩下的乘客数量 + 当前占用的车厢 < M，说明怎么也填不满了，回溯
    int current_occupied = 0;
    for(int i=1; i<=M; i++) if(box[i] > 0) current_occupied++;
    if(current_occupied + (N - p + 1) < M) return;

    // 遍历当前乘客 p 可以进的所有车厢
    for (int i = 1; i <= M; i++) {
        box[i]++;
        dfs(p + 1);
        box[i]--; // 回溯
    }
}

int main() {
    cin >> N >> M;
    dfs(1);
    cout << ans << endl;
    return 0;
}

---

难度评估

• GESP 4级：通常考察数组和简单循环，此题略难，因为涉及两层逻辑或递归。
• GESP 5级：完美契合。考察基本算法思想（穷举/搜索/简单DP），数据范围小，允许 $O(M^N)$ 的暴力解法通过，是检验递归思维的好题。