组合八题解析

约定：
1.\(1\le N, M\le 1000\)
2.所有答案对 \(10^6 +7\) 取模
3.每道题只有一个点，一个点有多组数据
4.输入格式：第一行整数 \(T(T\le 10)\)，表示数据组数；接下来 \(T\) 行每行两个数表示 \(N, M\)
5.时间限制为 \(\text{1s}\)，空间限制为 \(\text{256Mb}\)
6.文件名为 X.pas/c/cpp，输入为 X.in，输出为 X.out{大写字母}

A

给定 \(N\) 个不同的球，放进 \(M\) 个不同的盒子，盒子允许为空，有多少种方案？

显然，答案为 \(M ^ N\)

B

给定 \(N\) 个不同的球，放进 \(M\) 个不同的盒子，盒子不允许为空，有多少种方案？

Stirling 数，洛谷原题 \(\text{P1287}\)

C

给定 \(N\) 个不同的球，放进 \(M\) 个相同的盒子，盒子允许为空，有多少种方案？

首先，不考虑空盒子的方案，见 D，\(dp_{n, m}\) 表示 \(n\) 个球，\(m\) 个盒子的方案数。
因为可以有空盒子，枚举不为空的盒子数量

\[\text{ans} = \sum_{i = 1}^m dp_{n, i} \]

D

给定 \(N\) 个不同的球，放进 \(M\) 个相同的盒子，盒子不允许为空，有多少种方案？

\(dp_{n, m}\) 表示 \(n\) 个球，\(m\) 个盒子的方案数。

• 第 \(n\) 个球可以放在任意一个盒子，方案数 \(dp_{n - 1, m}\times m\)
• 第 \(n\) 个球单独放一个盒子，方案数 \(dp_{n - 1, m - 1}\)，因为盒子相同。
  则 \(dp_{n, m} = dp_{n - 1, m}\times m + dp_{n - 1, m - 1}\)

E

给定 \(N\) 个相同的球，放进 \(M\) 个不同的盒子，盒子允许为空，有多少种方案？

插板法

\[\text{ans} = \binom{n + m - 1}{m - 1} \]

F

给定 \(N\) 个相同的球，放进 \(M\) 个不同的盒子，盒子不允许为空，有多少种方案？

依旧插板法

\[\text{ans} = \binom{n - 1}{m - 1} \]

G

给定 \(N\) 个相同的球，放进 \(M\) 个相同的盒子，盒子允许为空，有多少种方案？

由于球和盒子均相同，假设所有盒子最终按所含球数降序排序。
\(dp_{n, m}\) 表示 \(n\) 个球，\(m\) 个盒子的方案数。

• 第 \(m\) 个盒子不放球，方案数为 \(dp_{n, m - 1}\)
• 第 \(m\) 个盒子放球，根据方案的递减性，所有盒子都要放球，方案数为 \(dp_{n - m, m}\)。
  则 \(dp_{n, m} = dp_{n, m - 1} + dp_{n - m, m}\)

H

给定 \(N\) 个相同的球，放进 \(M\) 个相同的盒子，盒子不允许为空，有多少种方案？

同 G，由于盒子不能为空，先把 \(m\) 个球放在每个盒子里，剩下 \(n - m\) 个球，就跟 G 一样了。