当小球遇上盒子

小球和盒子是非常经典（烂大街）的一种模型，以小球和盒子的爱恨情仇为背景，对把小球放到这个盒子里还是那个盒子里进行的一系列哲学问题探讨以及珂学形态分析，其中基本会涉及到组合数学（雾）和计数DP（雾）。 其实这种问题应该有很多博客进行过讲解，可能会大同小异，我尽量说的稍微详细一点，并补充一些其他内容。 文章有部分借鉴于其他大佬的博客和学长的题解，但主要内容都是我自己写的 可能会有一些错误，还请指出 作者很菜，本文可能过于基础，仅供萌新学习巩固，大佬愉悦身心 特别感谢 @ComeIntoPower 对本文的宝贵意见 ------------ ------------ **前置技能** **组合数公式** ~~（这东西应该大家都会吧）~~ $C_n^m=\frac{n!}{m!(n-m)!}$ 也可以使用递推式(杨辉三角) ~~组合数裸题（逃）~~ [P2822 组合数问题](https://www.luogu.org/problemnew/show/P2822) **插板法** (隔板法?) (插空法?)：主要运用于组合数学中，是排列组合的推广，主要用于解决不相邻组合与追加排列的问题。 就是在 $n$ 个物品之间插上 $m$ 个板，将其分为 $m+1$ 组。 （插板法） 用组合数可以轻松求出答案。 **捆绑法**：在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个大元素进行排序，然后再考虑大元素内部各元素间顺序的解题策略就是捆绑法． 感觉有点类似于物理的整体法与隔离法？ 例子：有$8$本不同的书；其中数学书$3$本，外语书$2$本，其它学科书$3$本．若将这些书排成一列放在书架上，求数学书和外语书都放在一起的方案数 把$3$本数学书“捆绑”在一起看成一个整体，$2$本外语书也“捆绑”在一起看成一个整体，与其它$3$本书一起看作$5$个元素，然后就可以求了 **容斥原理**：在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理 也就是我们小学学过的数学问题：一个班级里有$a$个人会打篮球，有$b$个人会踢足球，有$c$个人既会打篮球又会踢足球，询问这个班里会打篮球或会踢足球的有多少人？ $ans=a+b-c$ 化成式子为 $A∪B=A+B-A∩B$ ，以此类推 ------------ ------------ 接下来我们回到正题，默认问题为 $n$ 个小球放到 $m$ 个盒子里，题型共有三项要求，球是否相同，盒子是否相同，能否有空盒。 ### 1.球相同，盒子不同，不能有空盒 我们经过一波~~巧妙地~~的分析之后，发现这个问题的实质就是把 n 个小球分为 m 组（不能空），然后就这么转化成了一个组合数问题 $$ ans=C^{m-1}_{n-1}$$ 其实这就是一个插板法，就是在 n 个小球的 n-1 个空隙当中刚好插入 m-1 个板子，即恰好分为不为空的 m 组。 因为盒子不相同，所以 $(1,2)$ 和 $(2,1)$ 是不同的。 ### 2.球相同，盒子不同，可以有空盒 对于每个盒子，我们都给他一个球，那么上一个问题就和这问题一样了，所以我们可以看做自己有 n+m 个小球，然后我们在排列完之后在每一组都删去一个小球，这样就能枚举出有空盒的情况了。于是答案为 $$ ans=C^{m-1}_{n+m-1}$$ ### 3.球不同，盒子不同，可以有空盒 对于每一个球，你都可以放到 1~m 的任意一个位置,由于球不同，所以球与球之间是独立的。因为每个球有 m 种情况，所以我们得出 $$ans=m^n$$ ### 4.球不同，盒子相同，不能有空盒 对于这个问题有一种神奇的东西叫做第二类斯特林数（不是加特林） 在数学领域，斯特林数分为第一类斯特林数和第二类斯特林数，我们在这里只说第二种 第二类斯特林数（简称为S2）的定义为将n个物体划分成k个非空的没有区别的集合的方法数，大致就是把 n 个不同的小球放入m个相同的盒子中（且盒子不能为空）的方案数。递推公式为 $S2[i][j]=S2[i-1][j]*j+S2[i-1][j-1]$ （$S2[i][j]$ 表示前$i$个小球放到前$j$个盒子里的方案数） 我们可以这样理解：对于一个 $S2[i][j]$，你接下来要再放一个小球，你可以放到前$j$个盒子里，方案数为 $j*S2[i][j]$ ，也可以放到下一个盒子里，方案数为 $S2[i][j+1]$ 于是我们就可以得出上面的递推公式了，代码如下： ```cpp int n=read(),m=read(); S2[0][1]=1; for(int i=0;i<=n;i++){ for(int j=1;j<=i;j++){ S2[i][j]=(S2[i-1][j]*j+S2[i-1][j-1]); } } cout<<S2[n][m]<<endl; ``` 这个公式是$(n^2)$ 的，斯特林数还有一个公式 $S2(n,m)=\frac{1}{m!}*\sum_{k=0}^{m}(-1)^k$ $m \choose k$ $*(m-k)^n$ 如果集合没有非空的限制，方法有 $m^n$ 种 我们枚举为空的盒子，可得出 $m \choose k$ $*(m-k)^n$这部分是多出来的 但可能会重复，我们需要套一个容斥即 $(-1)^k$ 最后除一个$m!$消掉有序性，如果不除就是有序的 据说可以用FFT（快速傅里叶变换）加速，但是我太菜了不会，于是不提  ### 5.球不同，盒子也不同，不能有空盒 事实上这种情况与上面唯一的不同就是有序性，我们只需要在那个公式里不除$m!$，即在第二类斯特林数上乘上一个 $m!$ 就可以了。 $$ans=m!*S2[n][m]$$ ### 6.球不同，盒子相同，可以有空盒 因为可以有空盒，我们可以枚举每次一共用了几个盒子，然后把相应的第二类斯特林数加起来就可以了 $$ans=\sum_{i=1}^mS2[n][i]$$ 似乎这种数的名字叫做贝尔数 Bell数的定义：第n个Bell数表示集合{1,2,3,...,n}的划分方案数 看起来是不是和第二类斯特林数有点像。 可以说贝尔数就是其对应的第二类斯特林数之和。 贝尔数的相应公式为 $B_{n+1}=\sum_{k=0}^{n}$ $n \choose k$ $B_k$，即枚举包含最后一个元素的集合大小 也可以通过对应的第二类斯特林数求和得到，公式如下 $B_n=\sum_{k=1}^nS2(n,k)$ ### 7.球相同，盒子相同，可以有空盒 设 $f[n][m]$ 为 $n$个球放到 $m$ 个盒子里的方案数 如果只有一个盘子或者没有小球，方案数自然为$1$ 如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移 $f[i][j]=f[i][i]$ 如果小球比盒子要多，就分为将盘子放满和没放满两种情况，即$f[i][j]=f[i-j][j]+f[i][j-1]$ 总结上面三种情况就可以得出转移方程了，代码如下 ```cpp int n=read(),m=read(); for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ if(j==1 || i==0) f[i][j]=1; else if(i<j) f[i][j]=f[i][i]; else if(i>=j) f[i][j]=f[i-j][j]+f[i][j-1]; } } printf("%d\n",f[n][m]); ``` 实际上这个问题等价于自然数拆分问题，按管理大大的说法可以用五边形数解决，但是我太菜了不会五边形数。 ### 8.球相同，盒子相同，不能有空盒 有点类似于第一、二种情况之间的关系。 我们先假设在每一个盒子里都放上了一个球，就跟上面的情况一样了。 $$ans=f[n-m][m]$$ ------------ ------------ 以上应该是盒子小球最基础的八种情况了， 例题1[P1287 盒子与球](https://www.luogu.org/problemnew/show/P1287)，这道题就是前面的一种情况的裸题。 例题2[P2386 放苹果](https://www.luogu.org/problemnew/show/P2386)，又一道 例题3[P1025数的划分](https://www.luogu.org/problemnew/show/P1025)，又一道 这几道题都不是很难，用 dfs 也可以过，但还是建议打个DP理解一下 ------------ ------------ 本篇文章还没有结束（我还能水） 由于本文主题是盒子和小球，下面介绍几道 $noi$ 题库里的关于盒子和小球的题，结合学长的题解和我的个人理解，做法可能比较复杂，供大家参考 [盒子与小球二](http://noi.openjudge.cn/ch0206/9284/) 题面：N个有差别的盒子（1<=N<=20）。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球，也可以只放一种，也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法。 我们将红球和蓝球分别讨论，于是设计状态为$f[i][j][k]$表示前$i$个盒子里一共放了$j$个红球和$k$个蓝球的方案数 考虑转移 我们可以在第$i$个盒子里放若干个红球和蓝球，那么我们转移的过程就是枚举在这个盒子里放红蓝球数量不同的方案数 ```cpp int n=read(),A=read(),B=read(); f[0][0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=A;j++){ for(int k=0;k<=B;k++){//枚举状态 for(int a=0;a<=j;a++){//在i这里放了a个A球 for(int b=0;b<=k;b++){//在i这里放了b个B球 f[i][j][k]+=f[i-1][j-a][k-b];//状态转移 } } } } } ``` 因为题目要求中说球不必都放到箱子里面，所以统计答案时要枚举$A$球$B$球放入箱子的数量 但我们也可以多给它一个箱子，那些没有放在箱子里的球全都放在第n+1个箱子里，就省去了最后的统计答案。 ```cpp for(int i=1;i<=n+1;i++){ for(int j=0;j<=A;j++){ for(int k=0;k<=B;k++){ for(int a=0;a<=j;a++){ for(int b=0;b<=k;b++){ f[i][j][k]+=f[i-1][j-a][k-b]; } } } } } cout<<f[n+1][A][B]; ``` 这样做复杂度有一点爆炸（$n^5$） 但是过掉这道题还是绰绰有余的 感谢管理大大的提示，其实这题还有很简单的做法。 因为 $A$ 球和 $B$ 球是互不干涉的，我们可以分别考虑，算出放 $A$球的方案数和放 $B$ 球的方案数。对于红球，在 $N$ 个不同的箱子里可放任意个数，相当于一共有 $N+A$ 个球，我们从中选出 $N$ 个，B球同理。将得到的答案相乘 $ans=$ $n+A\choose n$ $n+B \choose n$ [盒子与小球三](http://noi.openjudge.cn/ch0206/9285/) 有N个相同的球，M个不同的盒子，每个盒子最多放K个球 ，请计算将这N个球全部放入盒子中的方案数模1000007后的结果 ，N<=5000，M<=5000。 这道题中每个盒子里能放的球是有上限的，我们设计状态 $f[i][j]$ 为前$i$个盒子里放$j$个小球的方案数 如果我们的转移方程为 $f[i][j]=\sum_{l=0}^{k}f[i-1][j-l]$的话，那么复杂度是三维的，会T掉 所以我们要对这个$\sum$进行降维打击 我们注意到对于$j$和$j+1$，它们的$\sum$只在左端点和右端点有出入 类似于维护一个队列，我们维护一个队列的和，右端点进左端点出，在j增加后，我们令$sum=sum-F[i-1][j-k]+F[i-1][j+1]$，这样就做到了O(1)转移，复杂度就不会挂掉了，代码如下： ```cpp int n=read(),m=read(),k=read(); for(int i=0;i<=m;i++) f[i][0]=1; for(int i=1;i<=m;i++){ int sum=i; for(int j=1;j<=n;j++){ f[i][j]=sum; sum+=f[i-1][j+1];//进队 sum%=mod; if(j-k>=0) {//出队 sum-=f[i-1][j-k]; sum=(sum+mod)%mod; } } } cout<<f[m][n]<<endl; ``` 根据管理大大的说法，这道题目可以用容斥的方法解决。因为每个盒子里能放的球有上限了，我们每次枚举 $i$ 个盒子超出限制，答案为 $\sum_{i=0}^m(-1)^i$ $m\choose i$ $n-i*(k+1)+m-1\choose m-1$ [盒子与小球四](http://noi.openjudge.cn/ch0405/9286/) 题面：给定N个各不相同的小球，和M个不同的BOX，有多少种不同的放球方法，使得每个BOX里的小球个数不小于Ｋ。N,M,K均小于15。 这道题和上道题不同的是每个盒子里能放的球的数量是有下限的，而且小球是不同的 设 $f[i][j]$ 表示前 $i$ 个盒子放了 $j$ 个球的方案数，我们每次转移的时候从 $k$ 开始枚举就可以了。 $f[i][j]=\sum_{l=k}^{j}f[i-1][j-1]*C_{n-(j-l)}^l$ ```cpp for(int i=k;i<=n;i++){ f[1][i]=C(n,i); } for(int i=2;i<=m;i++){ for(int j=k;j<=n;j++){ for(int l=k;l<=j;l++){ f[i][j]+=C(n-(j-l),l)*f[i-1][j-l]; } } } cout<<f[m][n]<<endl;; ``` 不要问我为什么没有盒子与小球一啊我也想知道啊 ------------ ------------ 那么本文的内容就到这里了 盒子和小球问题主要是方案数问题，形式比较多样，但可以往最开始的那几种情况考虑。还需要一定的数学思维能力。 ps:如果题目没有让你 % 一个数的话，记得开 $long long$ ，不要问我怎么知道的 那个，话说，这种问题真的有人会考吗？