算法競賽中的小球放盒子問題
背景：寫題的時候遇到過很多關於這類問題的變種題，所以打算總結一下
問題分類
根據球是否不同，盒子是否不同，盒子是否為空，一共可以分為 \(2^{3}\) 種情況討論
Problem 1
題意
給定 N 個不同的球，放進 M 個不同的盒子，盒子允許為空，有多少種方案？
解析
從每個球的角度出發，每個球都有M种放法，所以就是 \(M^{N}\)
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
while(cin >> n >> m)
cout << qmi(m,n) << endl;
return 0;
}
Problem 2
題意
給定 N 個相同的球，放進 M 個不同的盒子，盒子不允許為空，有多少種方案？
解析
這個就是經典的隔板法問題，相當於把N個球用隔板分成M個部分
N個球有N-1個空隙，在空隙中選擇M-1個作為隔板將原來分成M個部分，所以答案是 \(C_{N-1}^{M-1}\)
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
int p = sp[a];
int q = sp[b];
int r = sp[a - b];
int res = p / q;
return res / r;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 15; i++) sp[i] = sp[i-1] * i;
while(cin >> n >> m){
cout << C(n-1,m-1) << endl;
}
return 0;
}
Problem 3
題意
給定 N 個相同的球，放進 M 個不同的盒子，盒子允許為空，有多少種方案？
解析
和問題2類似，只需要把隔板法變形一下。
我們可以假定每個隔板的右邊自帶了一個小球，那麼這樣總共就會有 N+M 個小球，選 M-1 個空隙，答案就是 \(C_{M+N-1}^{M-1}\)
每次插入板子後形成的組合，把右邊的球去掉，可以發現就是我們所需要的答案
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
while(cin >> n >> m){
cout << C(n+m-1,n) << endl;
}
return 0;
}
Problem 4
題意
給定 N 個相同的球，放進 M 個相同的盒子，盒子允許為空，有多少種方案？
解析
利用動態規劃解決，設 \(dp[i][j]\) 表示將i個小球放到j個盒子里的方案數，那麼初始化顯然有 \(dp[0][0] = dp[0][1] = …… = dp[0][m] = 1\)
轉移分兩種情況考慮，第一種就是允許有盒子為空的情況 那麼就是 \(dp[i][j-1]\)
第二種是不允許有空盒， 此時可以假定j個盒子里每個盒子已經有了一個球（或者可以理解為把每個盒子抽一個球之後再放回去）
這種方案數等價於 \(dp[i-j][j]\)
所以轉移方程就是 \(dp[i][j] = dp[i][j-1] + dp[i-j][j]\)
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int dp[20][20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
for(int i = 1; i <= 15; i++) dp[0][i] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
if(i >= j)
dp[i][j] = dp[i][j-1] + dp[i-j][j];
else dp[i][j] = dp[i][j-1];
}
}
while(cin >> n >> m){
cout << dp[n][m] << endl;
}
return 0;
}
Problem 5
題意
給定 N 個相同的球，放進 M 個相同的盒子，盒子不允許為空，有多少種方案？
解析
跟第4個問題幾乎一樣，轉移方程也一樣，只不過這次變成了盒子不能為空
那麼最後的答案就是 \(dp[n-m][m]\) （即假定每個盒子已經有一個球了）
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int sp[20];
int dp[20][20];
int qmi(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int C(int a,int b){
if(b > a) return 0;
else return sp[a] / sp[b] / sp[a-b];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 20; i++) sp[i] = sp[i-1] * i;
for(int i = 1; i <= 15; i++) dp[0][i] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
if(i >= j)
dp[i][j] = dp[i][j-1] + dp[i-j][j];
else dp[i][j] = dp[i][j-1];
}
}
while(cin >> n >> m){
if(n >= m)
cout << dp[n-m][m] << endl;
else cout << 0 << endl;
}
return 0;
}
Problem 6
題意
給定 N 個不同的球，放進 M 個相同的盒子，盒子不允許為空，有多少種方案？
解析
依然採用動態規劃解決，設 \(dp[i][j]\) 表示將i個小球放到j個盒子里的方案數
考慮兩種情況，第一種情況，多了一個空盒子，多出來的球就放這個空盒子里，即 \(dp[i-1][j-1]\)
第二種情況，多出來的球放到之前的盒子里，由於有j個相同的盒子，即 \(dp[i-1][j] \times j\)
所以轉移方程就是從 \(dp[i][j] = dp[i-1][j-1] + dp[i-1][j] \times j\)
其實這個是第二類斯特林數，存在通項公式可以優化時間複雜度，這裡不再贅述，有興趣的可以自己下來研究一下
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
cout << dp[n][m] << endl;
}
return 0;
}
Problem 7
題意
給定 N 個不同的球，放進 M 個相同的盒子，盒子允許為空，有多少種方案？
解析
跟第6個問題一樣，答案抽象出來其實是 \(\sum_{i=1}^ndp[n][i]\)
因為這裡的區別就是有盒子可以為空，那麼在第6個問題中 \(dp[n][j]\) 表示成把n個球放進j個盒子里的方案數，並且盒子不為空
其實在這個問題中就等價於有j個盒子不為空，而另外m-j個盒子為空的情況
題目鏈接
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
int res = 0;
for(int i = 1; i <= m; i++){
res += dp[n][i];
}
cout << res << endl;
}
return 0;
}
Problem 8
題意
給定 N 個不同的球，放進 M 個不同的盒子，盒子不允許為空，有多少種方案？
解析
可以先假定盒子都相同，問題轉化為問題6
然後考慮不同盒子的排列即可
最後答案是 \(M! \times dp[n][m]\)
題目鏈接
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int dp[20][20];
int sp[20];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
sp[0] = 1;
for(int i = 1; i <= 15; i++) sp[i] = sp[i-1] * i;
dp[0][0] = 1;
for(int i = 1; i <= 15; i++){
for(int j = 1; j <= 15; j++){
dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
}
}
while(cin >> n >> m){
cout << sp[m] * dp[n][m] << endl;
}
return 0;
}
