题解

思路推导

相同盒子意味着只关心把 $N$ 个不同元素划分成 $M$ 个非空集合的方案数。这正是第二类 Stirling 数，记作 $S(N,M)$。

做法

考虑球 $N$ 所在的盒子。若它加入已有的某个盒子，有 $M$ 种选择，并留下 $S(N-1,M)$ 种划分；若它单独形成新盒子，则其余球有 $S(N-1,M-1)$ 种划分。因此

边界为 $S(0,0)=1$，且 $M>N$ 时答案为零。预处理到 $100$ 后即可回答所有输入。答案可能远超固定宽度整数，需要使用任意精度整数。

在极小范围内，可以用受限增长序列完整枚举集合划分。若 $M=2$，还可把球分到两个带编号集合后除去盒子交换造成的重复，得到 $S(N,2)=2^{N-1}-1$。

正确性证明

所有合法划分按第 $N$ 个球是否单独成盒分成互斥两类。第一类中删去该球后仍有 $M$ 个非空盒，把球放回时可选其中任意一个；第二类中删去该球和它的单元素盒后恰有 $M-1$ 个非空盒。两类分别由递推式的两项精确计数，并覆盖全部方案。结合边界归纳可知预处理得到的每个值均为所求方案数。

复杂度分析

预处理进行 $O(100^2)$ 次任意精度整数运算，每组查询为 $O(1)$ 次表查询；空间复杂度为 $O(100^2)$ 个任意精度整数。