小球盒子模型总结
题目链接：洛谷十二重计数法。
设有 $n$ 个球，$k$ 个盒子：
- 球之间互不相同，盒子之间互不相同，可以空盒
根据乘法原理，答案就是 $k^n$ 。 - 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球
相当于每个球找一个没有被选过的盒子放进去，答案是 $k^{\underline{n}}$ ，即 $k(k-1)\cdots(k-n+1)$ 。 - 球之间互不相同，盒子之间互不相同，每个盒子至少装一个球
可以先把盒子视为相同：$n$ 个球放进 $k$ 个相同盒子、不能空盒，这就是第二类斯特林数 $S^k_n$ 的定义。最后由于盒子不同，再乘上一个排列数，因此答案就是 $k!S^k_n$ 。 - 球之间互不相同，盒子全部相同，可以空盒
枚举非空盒子数量，相当于第二类斯特林数一行求和：$\sum_{i=1}^{k}S^i_n$ 。 - 球之间互不相同，盒子全部相同，每个盒子至多装一个球
因为盒子相同，不论怎么放都是一样的，答案是 $[n\leq k]$（这是一个布尔运算式，若 $n\leq k$ 成立则取 $1$ ，否则 $0$）。 - 球之间互不相同，盒子全部相同，每个盒子至少装一个球
就是第二类斯特林数 $S_n^k$ 。 - 球全部相同，盒子之间互不相同，可以空盒
隔板法经典应用，$n+k-1$ 个球选 $k-1$ 个板，因此答案是 $\binom{n+k-1}{k-1}$ 。 - 球全部相同，盒子之间互不相同，每个盒子至多装一个球
盒子不同，相当于要选出 $n$ 个盒子装球，因此答案是 $\binom{k}{n}$ 。 - 球全部相同，盒子之间互不相同，每个盒子至少装一个球
隔板法经典应用，$n-1$ 个空隙选 $k-1$ 个插板（可以看作是情况7时每个盒子里都预先加入一个球），因此答案是 $\binom{n-1}{k-1}$ 。 - 球全部相同，盒子全部相同，可以空盒
定义划分数 $p_{n,k}$ 表示将自然数 $n$ 拆成 $k$ 份的方案数，那么本例的结论就是 $p_{n,k}$ 。这个问题有一个经典递推式：$p(n,k) = p(n,k-1) + p(n-k,k)$ 。意义是将 $j$ 个自然数 $+1$ 或者加入一个 $0$ 。下面给出一个代码实现：p[0][0] = 1; for (int i = 1; i <= n; i++) { p[0][i] = 1; for (int j = 1; j <= m; j++) { if (i >= j) { p[i][j] = add(p[i][j - 1], p[i - j][j]); } else { p[i][j] = p[i][j - 1]; } } } - 球全部相同，盒子全部相同，每个盒子至多装一个球
和情况5一致，就是 $[n\leq k]$ 。 - 球全部相同，盒子全部相同，每个盒子至少装一个球
显然也是一个划分数：$p_{n-k,k}$ 。
至此，所有情况都已经有了最劣 $O(nk)$ 的实现，可以在洛谷拿到 $40$ 分，本题的满分解法需要一些多项式操作，以后再写。