放球问题

编号球不同盒子不同空盒
1
2
3
4
5
6
7
8

一.球相同,盒子相同,允许空盒

设$dp[i][j]$为$i$个球$j$个盒子且允许空盒的方案数

初始化:对于球数为$0/1$的任意个盒子,方案数均为1(因为允许空盒子)

$dp[i][j]$一部分来自$dp[i][j-k]$,表示挑了$k$个空盒子

另一部分来自已经存在的盒子,既$dp[i-k][j]$

还有一部分把球放置于新的盒子中,既$dp[i-k][j-1]$

$dp[i][j]=\sum_k^j dp[i][j-k]+\sum_k^i dp[i-k][j]+\sum_k^i dp[i-k][j-1]$

然而这是错的吧..

需要注意到因为空盒子是一样的,既$n$个球放满了$m$个盒子和$n$个球放$m+i,i \gt 0$个盒子方案是一样的

(只要有$m$个盒子放置方法和前者相同,空盒子对答案的贡献就是1)

所以当$i\lt j$时,有$dp[i][j]=dp[i][j-1]$

剩下只需讨论$i \ge j $的情况

显然也有前面的结论,至少有一部分来自$dp[i][j-1]$

除此以外$j$个盒子都是至少有1个球的部分,那等价于对$i$个球拿掉$j$个后,就变成$i-j$个球,$j$个允许空盒子(至少0个球)的盒子的情况,这显然是个合法的子结构,所以这一部分可直接用$dp[i-j][j]$来表示

二.球相同,盒子相同,不允许空盒

按照套路,转换问题为$n-m$个球放入$m$个允许空盒的盒子的情况

三.球相同,盒子不同,不允许空盒

经典的插板法应用,也就是在$n$个物体的$n-1$个间隙插入$m-1$个板子,答案为$n-1\choose m-1$

四.球相同,盒子不同,允许空盒

按照套路,转换为不允许空盒的情况就能套三,那就让盒子至少都有1个球,既原来有$n+m$个球,所以答案为$n+m-1 \choose m-1$

五.球不同,盒子相同,不允许空盒

第二类斯特林数

$dp[n][m]$:把$n$个不同的物体放入$m$个不可区分的非空盒子的方案数

考虑最后一个物体

如果单独放入一个盒子,方案数为$dp[n-1][m-1]$

否则,该物体放入已经存在的任意$m$个盒子中(无空盒),此前方案数为$dp[n-1][m]$,由于物体是区分的,$m$种选择方法由乘法原理可知有$m \cdot dp[n-1][m]$的方案数

既答案为$dp[n][m]=dp[n-1][m-1]+m \cdot dp[n-1][m]$

六.球不同,盒子相同,允许空盒

不可区分的空盒子对相同非空盒子方案答案的贡献为1

所以可以枚举空盒子数$i$,答案为$\sum_{i=0}^{m-1}dp[n][i]$

(不可能全部空的对吧)

七.球不同,盒子不同,不允许空盒

对比问题5,对比盒子多搞个全排列即可

答案为$m! \cdot dp[n][m]$

八.球不同,盒子不同,允许空盒

(woc想复杂了)

每个球都可以xjb放,所以答案是$m^n$

标签: none

添加新评论