本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-11 09:23:08

$I$

显然 $m^n$。

$II$

让每个球去选盒子，显然为 $\mathcal{A}_m^n$。

$III$

与第二类斯特林数有关

式子为 $${n \brace m} m!$$。

但是，第二类斯特林数的递推式子是 $O(nm)$ 的，因此我们需要一些优化。

法一：容斥

考虑总数为 $m^n$ 然后考虑排除不合法的方案数。

我们可以固定一些盒子，让他们强制为空。

根据容斥的公式，那么不合法的，也就是有空盒的方案数即为

$$\sum_{k=1}^{m} (-1)^{k-1} {m\choose k}(m-k)^n$$

那么，我们可以得到，原问题的方案数可以不用第二类斯特林数，可以用容斥得到。

$$m^n-\sum_{k=1}^{m} (-1)^{k-1} {m\choose k}(m-k)^n$$ $$=\sum_{k=0}^{m}(-1)^{k} {m\choose k}(m-k)^n$$

完事

法二：

考虑总的方案数为枚举哪些盒子为非空

$$m^n= \sum_{k=0}^m{n \choose k}{n \brace k}k!$$

直接二项式反演

$${n \brace m}m!=\sum_{k=0}^{m}(-1)^{k} {m\choose k}(m-k)^n$$

$IV$

枚举有多少盒子非空。

$$\sum_{i=1}^{m} {n\brace i}$$

$V$

搞笑的，$[n\le m]$。

$VI$

第二类斯特林数的定义

可通过 $III$ 得到。

$VII$

隔板，$n+m-1\choose m-1$。

$VIII$

考虑选出哪些盒子装球，$m\choose n$

$IX$

隔板 $n-1\choose m-1$。

$X$

考虑 dp，设 $f_{i,j}$ 表示 $i$ 个球，$j$ 个盒子的方案数。

考虑新增一个盒子的方案数。

如果必须有空盒，那就加上一个空盒；不能有空盒，那就把已有的全部 $+1$.

$f_{i,j}=f_{i,j-1}+f_{i-j,j}$。

但是，这是 $O(nm)$ 的。

所以，我们要上多项式优化。

构造多项式 $F_i(x)=(f_{i,0}+f_{i,1}x+f_{i,2}x^2+f_{i,3}x^3+...)$

根据转移方程，则有

$F_i(x)=F_{i-1}(x)\times (1+x^i+x^{2i}+...)$

又根据生成函数

有 $F_i(x)=\frac{F_{i-1}(x)}{1-x^i}$

即 $$F_i(x)=\prod_{j=1}^i\frac{1}{1-x^j}$$

然后对这个东西取 $ln$，加回去再取 $exp$ 即可。

详见付公主的背包 (不会，暂时贺上)

$XI$

搞笑的，$[n\le m]$

$XII$

先令每个盒子里有一个，转化成了 $X$，答案是 $f_{n-m,m}$。

关于多项式的部分，先欠着。