参考：
基本模型
球盒模型可根据：
- 球与球之间是否相同
- 盒子与盒子之间是否相同
- 盒子是否能为空
分为\(2^3=8\)种基本模型
n个相同的球，k个相同的盒子，盒子可为空
int box0(int n, int k) {
if (!n) return 1;
if (!k) return 0;
if (n < k) return box0(n, n);
return box0(n - k, k) + box0(n, k - 1);
}
n个相同的球，k个相同的盒子，盒子不为空
int box1(int n, int k) {
if (n < k) return 0;
return box0(n - k, k);
}
n个相同的球，k个不相同的盒子，盒子可为空
隔板法：
考虑将\(k-1\)个隔板插入\(n\)个小球中，转换成隔板插入的方案数
将木板和隔板都当作物品，即将\(n+k-1\)个物品中选出\(k-1\)个作为隔板，方案数为\(C_{n+k-1}^{k-1}\)
const int N = 1010, mod = 1e9 + 7;
ll c[N][N];
void initC() {
c[0][0] = 1;
for (int i = 1; i <= 1000; ++ i) {
c[i][0] = 1;
for (int j = 1; j <= 1000; ++ j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
int box2(int n, int k) {
return c[n + k - 1][k - 1];
}
n个相同的球，k个不相同的盒子，盒子不可为空
隔板法：
隔板只能插入球与球的间隔，方案数为\(C_{n - 1}^{k-1}\)
int box3(int n, int k) {
return c[n - 1][k - 1];
}
n个不相同的球，k个相同的盒子，盒子可为空
从第二类斯特林数考虑：
盒子是相同的，考虑通过枚举一共几个非空盒子，即\(\sum_{k=0}^{n}{n \brace k}\)
int box4(int n, int k) {
ll res = 0;
for (int i = 1; i <= k; ++ i) res = (res + s[n][i]) % mod;
return res;
}
特别的当\(n \leq k\)时，答案为贝尔数，记作\(B_{n}\)
\[B_{n+1}=\sum_{k=0}^{n}C_{n}^{k}B_{k} \]\(B_{n+1}\)比\(B_{n}\)多一个元素\(a_{n+1}\)，考虑：
- 若这个元素单独划分为一类，剩下\(n\)个元素，共\(C_{n}^{0}B_{n}\)种方案
- 若这个元素与另一个元素划分成一类，剩下\(n-1\)个元素，共\(C_{n}^{1}B_{n-1}\)种方案
- 若这个元素与另两个元素划分成一类，剩下\(n-2\)个元素，共\(C_{n}^{2}B_{n-2}\)种方法
- \(\cdots \cdots\)
贝尔数可通过贝尔三角形计算
\[\begin{aligned} & 1 \\ & 1\quad\qquad 2 \\ & 2\quad\qquad 3\quad\qquad 5 \\ & 5\quad\qquad 7\quad\qquad 10\,\,\,\qquad 15 \\ & 15\,\,\,\qquad 20\,\,\,\qquad 27\,\,\,\qquad 37\,\,\,\qquad 52 \\ & 52\,\,\,\qquad 67\,\,\,\qquad 87\,\,\,\qquad 114\qquad 151\qquad 203\\ & 203\qquad 255\qquad 322\qquad 409\qquad 523\qquad 674\qquad 877 \\ \end{aligned} \]- \(a_{0,0}=1\)；
- \(a_{n,1}=a_{n-1,n-1}\)
- \(a_{n,m}=a_{n,m-1}+a_{n-1,m-1}\)
\(a_{n,1}\)即为\(B_{n}\)
void initBell(int n) {
bell[0][0] = 1;
for (int i = 1; i <= n; ++ i) {
bell[i][0] = bell[i - 1][i - 1];
for (int j = 1; j <= n; ++ j)
bell[i][j] = (bell[i][j - 1] + bell[i - 1][j - 1]) % mod;
}
}
n个不相同的球，k个相同的盒子，盒子不可为空
第二类斯特林数（斯特林子集数）\(n \brace k\)，也记作\(S(n, k)\)，表示将\(n\)个不同的元素划分为\(k\)个非空子集的方案数
\[{n \brace k}={n-1 \brace k-1}+{k}{n-1 \brace k} \]即插入一个元素，可以：
- 将元素单独放入一个集合
- 将元素放入一个现有的集合
void initS2() {
s[0][0] = 1;
for (int i = 1; i <= 1000; ++ i)
for (int j = 1; j <= 1000; ++ j)
s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j] % mod) % mod;
}
int box5(int n, int k) {
return s[n][k];
}
n个不相同的球，k个不相同的盒子，盒子可为空
ll qpow(ll a, ll b) {
a %= mod;
ll res = 1;
while (b) {
if (b & 1) res = (res * a) % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int box6(int n, int k) {
return qpow(k, n);
}
n个不相同的球，k个不相同的盒子，盒子不可为空
类似于\(n\)个不相同的球，\(k\)个相同的盒子，盒子不可为空，只不过此时盒子不相同
可以类比成将球先装入\(k\)个相同且不为空的袋子，再将袋子放入盒子，总的方案数为\({n \brace k} \times k!\)
void initFac() {
fac[1] = 1;
for (int i = 2; i <= 1000; ++ i) fac[i] = i * fac[i - 1] % mod;
}
int box7(int n, int k) {
return s[n][k] * fac[n] % mod;
}
To Be Continue\(\dots \dots\)
标签：盒子,相同,int,qquad,模型,元素,return,球盒 From： https://www.cnblogs.com/Panmaru/p/17579050.html