题解 P5824 【十二重计数法】

经典球盒模型大合集题。很久之前自己就整理过类似的东西，今天突然发现洛谷上有这么个题，来水一篇题解。

注意，下面的讲解顺序不完全按照题目中的顺序。讲解不是非常详细，需要读者对计数原理有基本了解。

每个球都可以独立选择 $m$ 个盒，答案是 $ans_1=m^n$ 。

在问题 II 中球不同，按顺序把每个球所在的盒的编号排出来，相当于在 $m$ 个数里选 $n$ 个组成排列，答案就是 $ans_2=A(m,n)=\frac{m!}{(m-n)!}$ 。

如果球相同还要除以球的顺序，相当于在 $m$ 个数里选 $n$ 个数没有顺序，那么 $ans_8=C(m,n)=\frac{m!}{n!(m-n)!}$ 。

如果 $n>m$ 必然放不进去，否则所有合法方案都没区别，只有一种方案，那么 $ans_5=ans_{11}=[n\le m]$ 。

对于问题 IX 盒非空，考虑把 $n$ 个球摆成一排然后在中间插 $m-1$ 个板子（相邻两个球只间最多插一个板子），插好后相邻两个板子之间的球放入一个盒，这样盒是有顺序的。那么就是在 $n-1$ 个空位选出 $m-1$ 个位置放板子，有 $ans_9=C(n-1,m-1)$ 。

如果盒可以为空，先增加 $m$ 个球按照问题 IX 求出来，然后把每个盒里拿出来一个球，这时就是盒可空的方案数了。拿出来球是不影响方案数的，即 $ans_7=C(n+m-1,m-1)$ 。

先看问题 X。设 $n$ 个相同球分入 $m$ 个相同盒的方案数是 $T(n,m)$ 。按照有没有空盒来分类，如果有空盒就去掉这个空盒（加号左边），如果没有就所有盒取出一个球（加号右边），可以得到递推式 $T(n,m)=T(n,m-1)+T(n-m,m)$ 。

它是一个背包的形式，等价于用重量为 $1,2,3\dots m$ 的物品填满容量为 $n$ 的完全背包的方案数。

对它的第 $m$ 列做生成函数，这个很好推就不在这里推了，直接写出结果：

G_m(x)=\sum_{n=0}^\infty T(n,m)x^n=\prod_{i=1}^m\frac{1}{1-x^i}

ans_{10}=[x^n]G_m(x)

那么这个东西该怎么处理呢？请参见模板题P4389 付公主的背包及其下的题解。

对于问题 XII, 类似问题 VII 的处理方法，这回我们要先减少 $m$ 个球，然后按照问题 X 算，然后再把每个盒里加一个球。答案是 $ans_{12}=[x^{n-m}]G_m(x)$ 。

这两个问题本质上是一样的。这里给出第二类斯特林数的定义： $S_2(n,m)$ 是 $n$ 个不同元素分成 $m$ 个非空集合的方案数。

根据定义 $ans_6=S_2(n,m)$ 。我们可以先求问题 III，盒是有区别的，枚举有多少个盒是空的，容斥计算：

ans_3=\sum_{i=0}^m(-1)^iC(m,i)(m-i)^n

因为球有区别，此时每个盒都是独一无二的，所以可以直接除去盒的顺序：

ans_6=S_2(n,m)=\frac{1}{m!}ans_3=\frac{1}{m!}\sum_{i=0}^m(-1)^iC(m,i)(m-i)^n

这就是第二类斯特林数的通项公式，关于它的更多性质和应用可以自行上网搜索资料。

考虑对于每一种方案，放完之后都把所有空盒扔掉，剩下的盒不超过 $m$ 个。那么就相当于 $n$ 个不同的球放到不超过 $m$ 个非空盒子里的方案数，直接用上面的第二类斯特林数做和就可以了。

ans_4=\sum_{i=0}^mS_2(n,m)

如何快速求第二类斯特林数的一行呢，注意到这个通项公式展开后是一个卷积的形式，可以用 NTT 优化卷积。具体做法参见另一道模板题P5395 第二类斯特林数·行及其下的题解。顺便说一句，当 $m\ge n$ 的时候，它就是贝尔数。

毕竟是式子题，代码就不放了。