当小球遇上盒子
一套排列组合题：盒子是否相同，球是否相同，能否有空盒子共8个状态
PS：代码上\(f,g\)的两个维度是反着写的
PS：\({n\choose m}=\frac{n!}{m!(n-m)!}=C_n^m\)
盒不同，球相同，不为空
现在有\(r\)个互不相同的盒子和\(n\)个相同的球，要将这\(n\)个球放入\(r\)个盒子中，且不允许有空盒子，问有多少种放法
既然球相同，不妨排成一列，这样我们就可以把盒子看做分隔符。
这样问题就变成了：选出\(r-1\)个分隔符的选法。
一共有\(n-1\)个分隔符，所以答案为：
\[{n-1\choose r-1} \]int r,inv[15],jc[15],n;
int main(){
cin>>n>>r;
jc[1]=jc[0]=1;for(int i=2;i<=12;i++)jc[i]=jc[i-1]*i;
cout<<jc[n-1]/jc[r-1]/jc[n-r]<<"\n";
}
盒不同，球相同，能为空
这时候可能出现分隔符可以放一起的情况，怎么办呢？如何处理这种情况？
如果我们能转化为第一种情况，就好了，但如何转化呢？
不妨将分隔符也看做球，这样就可以转化了——Why？因为这时候等价于从\(n+r-1\)个物品里拿出\(r-1\)作为分隔符。答案即为：
\[{n+r-1\choose r-1} \]#define int long long
using namespace std;
int r,inv[25],jc[25],n;
int C(int n,int m){
return jc[n]/jc[m]/jc[n-m];
}
signed main(){
cin>>n>>r;
jc[1]=jc[0]=1;for(int i=2;i<=22;i++)jc[i]=jc[i-1]*i;
cout<<C(n+r-1,r-1)<<"\n";
}
盒相同，球不同，不能空
此问题等价于第二类斯特林数，考虑进行DP求解：
设\(f[i,j]\)表示\(i\)个盒子\(j\)个球不能空的方案数：
初始化：\(f[0,0]=f[1,1]=1\)
目标： \(f[r,n]\)
则考虑转移：
- 不新开盒子：\(if[i,j-1]\)：从\(i\)个盒子里找一个放进去
- 新开盒子：\(f[i-1,j-1]\)
转移：\(f[i,j]=if[i,j-1]+f[i-1,j-1]\)
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int f[105][105];
signed main(){
int n,m;cin>>n>>m;
f[1][1]=f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j]*j+f[i-1][j-1];
}
}
cout<<f[n][m]<<"\n";
}
盒相同，球不同，能为空
这个问题可以由于盒子是一样的，那么能为空的可以直接不管，类比上一个，可以得到其答案为：
\[\sum_{k=0}^if[k,n] \]#define int long long
int f[105][105];
signed main(){
int n,m;cin>>n>>m;
f[1][1]=f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j]*j+f[i-1][j-1];
}
}
int ans=0;
for(int i=0;i<=m;i++)ans+=f[n][i];
cout<<ans<<"\n";
}
盒不同，球不同，不能空
这个题可以换一个角度，与盒相同，球不同，不能空的情况相比，只是多了盒不同这一个限制。
那么大可以将这个盒子进行编号，然后就对这种情况进行计数即可。一共有\(r!\)种编号方式，所以答案为:\(r!f[r,n]\)
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int f[105][105];
signed main(){
int n,m;cin>>n>>m;
f[1][1]=f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j]*j+f[i-1][j-1];
}
}
int ans=1;for(int i=1;i<=m;i++)ans*=i;
cout<<f[n][m]*ans<<"\n";
}
盒不同，球不同，能为空
这玩意更屑了。
容易发现这玩意其实并不具备任何对方法进行限制的条件，也不需要去重。所以答案就是\(r^n\)
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
signed main(){
int n,m;cin>>n>>m;
int ans=1;for(int i=1;i<=n;i++)ans*=m;
cout<<ans<<"\n";
}
盒相同，球相同，能为空
这玩意还是考虑DP求解。
设\(g[i,j]\)表示\(i\)个盒子\(j\)个球的答案。
初始：\(g[i,0]=1\)
目标：\(g[r,n]\)
类比\(f\)的方法，还是考虑用新不新开来搞
- \(i\le j\)，
考虑对方案数分成两类：没有一个盒子为空与有盒子为空的方案数
没有盒子为空，可以考虑将所有盒子里都放一个球，方案数是\(g[i,j-i]\)
有盒子为空，直接加上\(g[i-1,j]\)，这时候新开的盒子是空的，满足题设
\(g[i,j]=g[i,j-i]+g[i-1,j]\)
- \(i>j\)，此时只能新开一个为空的(鸽巢原理)——为了去重(想一想，为什么/doge)
\(g[i,j]=g[i-1,j]\)
进行转移即可。
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int f[105][105];
signed main(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)f[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>=j)f[i][j]=(f[i-j][j]+f[i][j-1]);
else f[i][j]=f[i][j-1];
}
}
cout<<f[n][m]<<"\n";
}
盒相同，球相同，不为空
这时候类比之前的方法，给每个盒子预先放一个球，由于球和盒子是一样的，方案唯一
这样就变成了上一个问题，答案为\(g[r,n-r]\)
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int f[1005][1005];
signed main(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)f[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>=j)f[i][j]=(f[i-j][j]+f[i][j-1])%12345;
else f[i][j]=f[i][j-1];
}
}
cout<<f[n-m][m]%12345<<"\n";
}
延伸模型
模型1
给定\(n\)个相同的盒子，\(m\)个相同的球，每个盒子最少放\(t\)个，求方案数。
设\(f[i,j,k]\)表示\(i\)个盒子，\(j\)个球，每个盒子最少\(k\)个的方案数。
初始化：
- \(ik>j,f[i,j,k]=0\)
- \(k\le j,f[1,j,k]=1\)
- \(f[0,j,k]=0\)
注意三个限制条件是有优先级的
转移：
\(f[i,j,k]=\sum_{p=k}^jf[i-1,j-p,p]\)
目标：
\(f[n,m,t]\)
正确性：这个做法保证了在每一个方案里面盒子的排列是单调不增的。
方案数很大。
可以使用记忆化搜索完成
模型2
\(n\)个不同的盒子，\(m\)个相同的球，每个盒子至少放\(a_1,a_2\sim a_n\)个球。求方案数
解：设\(S=\sum_{i=1}^n(a_i-1)\)，则方案数为：\({m-S-1\choose n-1}\)
可以看作每个盒子预先放\(a_i-1\)个，问题转化为求盒子不为空的方案数。
模型3
\(n\)个不同的盒子，\(m\)个相同的球，每个盒子最多一个球，非空盒子不能相邻。
有解：\(2m-1\le n\)
标签：盒子,入门,相同,int,小球,long,计数,include,jc From： https://www.cnblogs.com/oierpyt/p/17113639.html