问题求解II-HW02 题解
Problem A: Twelvefold Way I
- 将 $n$ 个完全相同的球放入 $m$ 个不同的篮子，问有多少种不同的放法。
- $1\leq n, m\leq 1000$。
经典的组合数学问题。由于盒子可空，考虑对 $n+m$ 个球使用插板法，最后再从每个盒子里扣掉一个球，因此总方案数为 $\binom{n+m-1}{m-1}$。
因为本题数据范围较小，所以可以利用 $\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$ 的组合数递推公式来计算答案取模后的值。但我们仍然建议大家学习快速计算阶乘逆元的方法，以应对可能出现的更大的数据范围。你可以参考 这篇文章 学习求逆元的常见写法。
Problem B: Twelvefold Way II
- 将 $n$ 个各不相同的球放入 $m$ 个完全相同的篮子，且每个篮子里至少有一个球，问有多少种不同的放法。
- $1\leq n, m\leq 500$。
令 $s(n, m)$ 表示将 $n$ 个不同的球放入 $m$ 个相同的篮子的方案数，考虑最后一个球的放法：
- 该球独占一个篮子，则剩下的 $n-1$ 个球放在 $m-1$ 个篮子里，方案数为 $s(n-1, m-1)$。
- 该球不独占一个篮子，则先将剩下的 $n-1$ 个球放入 $m$ 个篮子里，再挑选一个篮子放入最后一个球，方案数为 $m\cdot s(n-1, m)$。
因此 $s(n, m)=s(n-1, m-1) + m\cdot s(n-1, m)$。这里的 $s(n, m)$ 称为第二类斯特林数，有兴趣的同学可以上网搜索与之相关的其他性质。