咕咕咕

这期注释比正文还长。

【算法漫笔006】浅谈盒子与球

这篇写了很久，主要原因是我比较懒这篇太长太难写了。
注释最多的一集。写的最长的一集。

盒子与球

盒子与球主要是一种排列组合，其问题形式为：将 $n$ 个球放入 $m$ 个盒子中，根据球是否相同^[1]、盒子是否相同、盒子中至少一个球/至多一个球/无限制的放球，组合成不同的计数问题。我们来一个个解析这些问题。

为了方便，我们将每个问题编码，第一位表示球相同（$1$）/不同（$0$），第二位表示盒子相同（$1$）/不同（$0$）。第三位表示盒子中无限制的放球（$A$）/至少一个球（$B$）/至多一个球（$C$）。

如果你对排列组合不太熟悉，以下的内容请配合注释理解。

00A

即球不同，盒子不同，无限制。

此时每个球都是独立的，可以放入任何一个盒子当中。根据乘法原理^[2]，此时总方案数为：

$$m^n$$

00B

即球不同，盒子不同，每个盒子至少放一个球。

此时我们可以先将 $n$ 个球分成 $m$ 个非空的无序集合，显然方案数为 $S(n,m)$^[3]。此时我们已经将 $n$ 个不同的球分成了 $m$ 个非空的无序集合，但题目要求盒子是不同的，所以我们还需要把这 $m$ 个集合分配给 $m$ 个不同的盒子。这相当于对 $m$ 个集合进行全排列^[4]，方案数为 $m!$。再次根据乘法原理得到：

$$S(n,m) \times m!$$

特别的，当 $n<m$ 时，我们无法保证每个盒子至少放一个球，故方案数为 $0$。

00C

即球不同，盒子不同，每个盒子至多放一个球。

因为每个盒子最多只能放一个球，所以先从 $m$ 个盒子中选出 $n$ 个来放球，方案数为$\binom{m}{n}$^[5]。然后将 $n$ 个不同的球与选出的 $n$ 个不同盒子一一对应（即全排列^[4:1]），方案数为 $n!$。根据乘法原理^[2:1]，总方案数为：

$$\binom{m}{n} \times n!=\frac{m!}{(m-n)!}$$

特别的，当 $n>m$ 时，我们无法保证每个盒子至多放一个球，故方案数为 $0$。

01A

即球不同，盒子相同，无限制。

此时盒子不可区分，但球仍可区分。我们需要将 $n$ 个不同的球分成不超过 $m$ 个非空^[6]无序集合。

此时我们可以枚举非空盒子的数量 $k$，其中 $k$ 从 $1$ 到 $\min⁡(m,n)$，对于每个 $k$，方案数为第二类斯特林数 $S(n,k)$^[3:1]。根据加法原理^[7]，总方案数为：

$$\sum_{k=1}^{\min(n,m)} S(n,k)$$

特别的，当 $n=0$ 时，方案数为 $1$（全空盒）；当 $m=0$ 时，若 $n=0$ 则方案数为 $1$，否则为 $0$。

01B

即球不同，盒子相同，每个盒子至少放一个球。

根据 $S(n,m)$^[3:2]的定义，答案为：

$$S(n,m)$$

特别的，当 $n<m$ 时，我们无法保证每个盒子至少放一个球，故方案数为 $0$。

01C

即球不同，盒子相同，每个盒子至多放一个球。

因为盒子相同，且每个盒子最多放一个球，所以实际上只有两种可能，即盒子能够放下和无法全部放下，即：

$$\begin{cases} 1&n\le m\\ 0&n>m \end{cases}$$

10A

即球相同，盒子不同，无限制。

此时球完全相同，但盒子可区分。也就是将 $n$ 个无区别的球放入 $m$ 个有编号的盒子，允许空盒。使用隔板法^[8]解决，答案为：

$$\binom{n+m-1}{m-1}$$

特别的，当 $n=0$ 时，方案数为 $1$（全空盒）；当 $m=0$ 时，若 $n=0$ 则方案数为 $1$，否则为 $0$。

10B

即球相同，盒子不同，每个盒子至少放一个球。

依然使用隔板法^[8:1]。先想象：给每个盒子放 $1$ 个球，此时这些盒子都欠我 $1$ 个球。剩下 $n-m$ 个球，问题转化为将 $n-m$ 个相同球放入 $m$ 个不同盒子（允许空盒），即 10A 的情形。因此方案数为：

$$\binom{(n-m)+m-1}{m-1}=\binom{n-1}{m-1}$$

特别的，当 $n<m$ 时，我们无法保证每个盒子至少放一个球，故方案数为 $0$。

10C

即球相同，盒子不同，每个盒子至多放一个球。

因为球相同且每个盒子最多一个，所以实际上就是从 $m$ 个不同的盒子中选出 $n$ 个来放球（每个盒子恰好一个球）。符合组合数^[5:1]的定义，答案为：

$$\binom{m}{n}$$

特别的，当 $n>m$ 时，我们无法保证每个盒子至多放一个球，故方案数为 $0$。

11A

即球相同，盒子相同，无限制。

此时球完全相同，盒子也完全相同。问题转化为：将整数 $n$ 拆分为至多 $m$ 个正整数之和^[9]。我们定义 dp 表示 $n,m$ 的整数拆分数^[10]，则答案为：

$$dp_{m,n}$$

特别的，当 $n=0$ 时，方案数为 $1$（全空盒）；当 $m=0$ 时，若 $n=0$ 则方案数为 $1$，否则为 $0$。

11B

即球相同，盒子相同，每个盒子至少放一个球。

依然先让每个盒子欠债一颗球，剩下 $n-m$ 个球。问题转化为将 $n-m$ 个相同球放入 $m$ 个相同盒子（允许空盒），即 11A 的情形。因此方案数为：

$$dp_{m,n-m}$$

特别的，当 $n<m$ 时，我们无法保证每个盒子至少放一个球，故方案数为 $0$。

11C

即球相同，盒子相同，每个盒子至多放一个球。

因为球相同且盒子相同，每个盒子最多一个球，所以实际只有两种可能，若盒子够用为 $1$，不够用为 $0$。

$$\begin{cases} 1&n\le m\\ 0&n>m \end{cases}$$

题目

总的来看还是有一定的套路的，我自己认为我写的还比较好懂。

洛谷P5824 十二重计数法

诶诶怎么是黑题？诶诶怎么要用 $FFT$！前面的区域以后再来探索吧。

洛谷T188453 十二重计数法【弱化版】

还是弱化版更适合我们！我们来写一下这个青题吧！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;//83517427
const int N=1e3+5;
int n,m,S[N][N],dp[N][N];
int slow_pow(int x,int y) {
    int res=1;
    while (y) {
        if (y&1) res=res*x%	MOD;
        x=x*x%MOD;
        y>>=1;
    }
    return res;
}
void init() {
    S[0][0]=1;
    for (int i=1;i<=N-5;i++) {
        S[i][0]=0;
        S[i][i]=1;
        for (int j=1;j<i;j++) {
            S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%MOD;
        }
    }
}
void init_dp() {
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for (int i=0;i<=N-5;i++) {
        for (int j=1;j<=N-5;j++) {
            if (i>=j) dp[i][j] =(dp[i][j-1]+dp[i-j][j])%MOD;
            else dp[i][j]=dp[i][j-1];
        }
    }
}
int jc(int n) {
	int res=1;
	for (int i=1;i<=n;i++) {
		res=(res*i)%MOD;
	}
	return res;
}
int C(int n,int m) {
    if(m<0||m>n) return 0;
    return jc(n)*slow_pow(jc(m),MOD-2)%MOD*slow_pow(jc(n-m),MOD-2)%MOD;
}
signed main() {
	init();
	init_dp();
	cin >> n >> m;
	cout << slow_pow(m,n)%MOD << endl;
	if (n>m) cout << "0\n";
	else {
    	int ans=1;
    	for (int i=0;i<n;i++) ans=ans*(m-i)%MOD;
    	cout << ans << endl;
	}
	if (n<m) cout << "0\n";
	else cout << (jc(m)*S[n][m])%MOD << endl;
	int ans=0;
	for (int i=1;i<=m;i++) {
		ans=(ans+S[n][i]%MOD);
	}
	cout << ans%MOD << endl;
	if (n<=m) cout << "1\n";
	else cout << "0\n";
	cout << S[n][m] << endl;
	cout << C(n+m-1,m-1) << endl; 
	if (n<=m) cout << C(m,n) << endl;
	else cout << "0\n";
	cout << C(n-1,m-1) << endl;
	cout << dp[n][m] << endl;
	if (n<=m) cout << "1\n";
	else cout << "0\n";
	if (n<m) cout << "0\n";
	else cout << dp[n-m][m] << endl;
	return 0;
} 

还不算很难！

题外话

好想写 DP 但是不知道怎么写，DP 这个东西太多变了，没有完整的流程，所以还是单开一个专题比较好，算法漫笔的第六篇还是写盒子与球吧。总之就是我还是写数论了

注释&致谢

感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。

---

1. 相同：在盒子与球模型里，相同和不同指的是物体本身是否可区分，例如，在球不同的情况下，将两个盒子中分别放入一个球，是一种方案，而将两个盒子中的球调换则是另一种方案。而在球相同的情况下，我们视以上两种方案为一种。 ↩︎

2. 乘法原理：即如果完成一件事需要 $n$ 个步骤，第 $i$ 个步骤有 $a_i$ 种不同的方法，且这些步骤互不影响，那么完成这件事总共有 $a_1 \times a_2 \times \dots \times a_n$ 种方法。 ↩︎ ↩︎ ↩︎ ↩︎

3. $S(n,m)$：$S(n,m)$ 为第二类斯特林数，$S(n,m)$ 表示将 $n$ 个不同元素划分为 $m$ 个非空无序集合的方案数，满足递推：$S(n,m)=S(n-1,m-1)+m \times S(n-1,m)。$其中：$S(n,1)=S(n,n)=1$公式的推导也很简单：考虑第 $n$ 个元素，其有两种情况：
   自己单独作为一个非空集合：那么剩余的 $n-1$ 个元素就要划分成 $m$ 个非空集合，根据定义方案数为：$S(n-1,m-1)$加入已有集合：先将前 $n-1$ 个元素划分成 $m$ 个非空集合，根据定义方案数为 $S(n-1,m)$。然后第 $n$ 个元素可以放入这 $m$ 个集合中的任意一个，有 $m$ 种选择。根据乘法原理^[2:2]得到：$m \times S(n-1,m)$最后根据加法原理^[7:1]得到递推公式：$S(n,m)=S(n-1,m-1)+m \times S(n-1,m)。$
   边界情况也很好理解，$S(n,1)=1$（全部元素只能放在一个集合里），$S(n,n)=1$（每个元素各自成一组）。 ↩︎ ↩︎ ↩︎

4. 全排列：即把 $m$ 个不同的元素按任意顺序排成一列，方案数为 $m!$。其定义是：从 $m$ 个不同元素中取出 $m$ 个，按顺序排列，共有 $m \times(m-1)\times\dots\times 1=m!$ 种方法。 ↩︎ ↩︎

5. 组合数：$\binom{m}{n}$ 表示组合数，即从 $m$ 个不同元素中选出 $n$ 个的方案数，计算公式为 $\frac{m!}{n!(m-n)!}$。公式的推导为：先从 $m$ 个元素中选 $n$ 个按顺序排列（排列数^[11] $\frac {m!} {(m−n)!}$​），但组合不考虑顺序，而 $n$ 个元素的内部顺序有 $n!$ 种，因此需要除以 $n!$，即：$\frac{m!}{n!(m-n)!}$ ↩︎ ↩︎

6. 非空：因为空盒在盒子相同时没有区别。 ↩︎

7. 加法原理：即在两种情况互不重叠时，总可能数就是两种情况的可能数相加。 ↩︎ ↩︎

8. 隔板法：即将问题转化为在多个球中插入隔板，计算隔板的排列。此时由于两个隔板不可能重合，所以可以保证每个集合非空。 ↩︎ ↩︎

9. 问题转化：因为盒子相同，空盒没有区别，所以只需关注非空盒子的个数。 ↩︎

10. 整数拆分数：这里定义的整数拆分数 $dp_{m,n}$，表示将正整数 $n$ 拆分为至多 $m$ 个正整数之和的方案数。可以依靠递推公式 $dp_{m,n}=dp_{m-1,n}+dp_{m,n-m}$。很好理解的递推公式此处不再解释。其中 $dp_{m​,0}=1$，当 $n<0$ 时 $dp_{m,n}=0$。 ↩︎

11. 排列数：即从 $m$ 个不同元素中取出 $n$ 个，按顺序排成一列，方案数为 $\frac{m!}{(m-n)!}$。它与组合数的区别在于：排列考虑顺序，组合不考虑顺序。第一个位置有 $m$ 种选择，第二个位置有 $m-1$ 种选择，……，第 $n$ 个位置有 $m-n+1$ 种选择，根据乘法原理^[2:3]，总方案数为 $m \times(m-1) \times \dots \times (m-n+1)=\frac{m!}{(m-n)!}$。 ↩︎