题解 P5824 【十二重计数法】

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

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

I 球不同盒不同

每个球都可以独立选择 mm 个盒,答案是 ans1=mnans_1=m^n

II, VIII 盒不同,盒最多放一个球

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

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

V, XI 盒相同,盒最多放一个球

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

VII, IX 球相同盒不同

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

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

X, XII 球相同盒相同

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

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

对它的第 mm 列做生成函数,这个很好推就不在这里推了,直接写出结果:

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

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

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

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

III, VI 球不同,盒非空

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

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

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

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

ans6=S2(n,m)=1m!ans3=1m!i=0m(1)iC(m,i)(mi)nans_6=S_2(n,m)=\frac{1}{m!}ans_3=\frac{1}{m!}\sum_{i=0}^m(-1)^iC(m,i)(m-i)^n

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

IV 球不同盒相同

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

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

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

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