不要引入斯特林数，$N^2$ 的斯特林数本质就是个简单递推，只会占用大脑的空间（所以我将数据范围开到 $10^5$ 了）。

考虑容斥。

首先，设 $F_n$ 为球不同，盒不同，可空的数量。

则显然有

$$F_n=m^n$$

容斥一下，钦定有 $k$ 个盒子是空的，则本题答案为

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

预处理阶乘及其逆元，复杂度 $\Theta(n)$。

结论

将 n 个不同的球 放入 m 个不同的盒子（每个盒子至少放 1 个球）的放法数为：

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

其中：

• $S(n, m)$ 是第二类斯特林数，表示将 n 个不同球划分为 m 个非空子集的方式数。
• $m!$ 是对盒子排列的，因为盒子有区别。

但是，注意到 $n,m \le 10^5$ ，$O(nm)$ 递推过不了。

结论2

其实这道题的答案还有一个表达式

$$\sum_{i=0}^{m} (-1)^i \cdot C_{m}^{i} \cdot (m-i)^n $$

解析：

考虑容斥：

• 假如允许空盒，有 $m^n$ 种方案
• 再减去一定有一个空盒的方案数 $C_{m}^{m-1} \cdot (m-1)^n$
• 再加上一定有两个空盒的方案数 $C_{m}^{m-2} \cdot (m-2)^n$
• ……

就推出来了

---

推论：第二类斯特林数的通项

由

$$m! \cdot S(n, m) = \sum_{i=0}^{m} (-1)^i \cdot C_{m}^{i} \cdot (m-i)^n $$

得

$$S(n, m) = \frac{1}{m!} \sum_{i=0}^{m} (-1)^i \cdot C_{m}^{i} \cdot (m-i)^n $$