本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-25 07:30:51

$n$ 个球，$m$ 个盒子，

盒相同，球相同，允许空

设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的方案数，有

$$f(i, j) = f(i - j, j) + f(i, j - 1)$$

由于球是不同的，所以我们不能单独考虑每个球的状态。这 $i$ 个球，要么每个都要放，也就是 $f(i - j, j)$，要么是至少一个不放，也就是 $f(i, j - 1)$。

最后答案是 $f(n, m)$。

盒相同，球相同，不许空

我们提前取出 $n$ 个球不放，于是方案数就是上一问的 $f(n - m, m)$。

盒相同，球不同，允许空

设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的放置

盒相同，球不同，不许空

盒不同，球相同，允许空

盒不同，球相同，不许空

盒不同，球不同，允许空

盒不同，球不同，不许空