P5824十二重计数法，如何为？

P5824 十二重计数法 大意 有 \(n\) 个球和 \(m\) 个盒子，球要全部装进盒子里。 \(\text{I}\)：球之间互不相同，盒子之间互不相同。 \(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。 \(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。 \(\text{IV}\)：球之间互不相同，盒子全部相同。 \(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。 \(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。 \(\text{VII}\)：球全部相同，盒子之间互不相同。 \(\text{VIII}\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。 \(\text{IX}\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。 \(\text{X}\)：球全部相同，盒子全部相同。 \(\text{XI}\)：球全部相同，盒子全部相同，每个盒子至多装一个球。 \(\text{XII}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。 思路 \(\text{I}\)：球之间互不相同，盒子之间互不相同。 显然答案是 \(m ^ n\)。 \(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。 每次选择一个没装过球的盒子，答案就是 \(m ^ {\underline{n}}\)。 \(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。 第一种方式理解： 我们先考虑把 \(n\) 个不同的球，放在 \(m\) 个相同的盒子里，且盒子不为空，那么这样的答案就是第二类斯特林数，答案为 \(n \brace m\)，可是这个题的盒子是不相同的，我们将盒子编上号，再乘上 \(m!\) 的贡献，答案就是 \(m! {n \brace m}\)。 第二种方式理解： 我们采用容斥原理，全集即为 \(n\) 个不同的球随意的放入 \(m\) 个不同的盒子里，答案就是 \(m ^ n\)，但是我们要求盒子不为空，我们知道至少 \(k\) 个盒子为空的方案数即为 \(\binom{m}{k} (m - k) ^ n\)，容斥一下，故最终答案就是 \(\sum_{k = 0} ^ {m} (-1) ^ k \binom{m}{k} (m - k) ^ n\)。 \(\text{IV}\)：球之间互不相同，盒子全部相同。 我们可以先看 \(\text{VI}\)。 看完 \(\text{VI}\) 之后，我们发现区别就是这个盒子可以为空，我们只需要枚举几个盒子里面装了球，则答案是 \(\sum_{i = 1} ^ m {n \brace i}\)，就是同一行的和，直接用卷积算出来第 \(m\) 行的系数，答案就是将这一行加起来。 \(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。 盒子全部相同，放哪都行，答案本质上都是一样的，即为 \([n \le m]\)。注：\([]\) 表示艾弗森括号。 \(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。 这个就是经典的第二类斯特林数，表示的就是 \(n\) 个不同的球放到 \(m\) 个相同的盒子里，盒子必须非空的方案数，就是 \(n \brace m\)，对于第二类斯特林数，我们可以采用递推的求法，\({n \brace m} = {n - 1 \brace m - 1} + m {n - 1 \brace m}\)，这个是什么意思呢？首先 \({n - 1 \brace m - 1}\) 的意思是开个新盒子，\(m {n - 1 \brace m}\) 就是用旧的盒子。 对于 \(\mathcal{O}(nm)\) 的做法，我们可以考虑直接递推，但是如果是 \(\mathcal{O}(n \log n)\) 就需要更厉害的做法了。