题目链接

将 个球放进 个盒子，求方案数（不计放球的先后顺序）。

：球之间互不相同，盒子之间互不相同。
：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

：球之间互不相同，盒子全部相同。
：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

：球全部相同，盒子之间互不相同。
：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

：球全部相同，盒子全部相同。
：球全部相同，盒子全部相同，每个盒子至多装一个球。
：球全部相同，盒子全部相同，每个盒子至少装一个球。

答案对 取模。

I

显然答案为 。

II

显然答案为 。

III

显然答案为 。

这里 为第二类斯特林数，表示将 个元素划分为 个互不区分的集合的方案数。

考虑计算第二类斯特林数，首先根据组合意义：

做二项式反演：

顺便，这个玩意有 的递推：

IV

显然答案为 。

因此根据 中得到的式子做卷积即可。

V

显然答案为 。

VI

显然答案为 。

VII

插板法，显然答案为 。

VIII

显然答案为 。

IX

继续插板，答案为 。

X

设 表示将 写成不增的 个非负整数和的方案数，则 即为所求。

显然有

令 为主元，考虑 的生成函数

由递推式，有

因此

考虑求其多项式 ，将乘法转化为加法，然后再 回去。

令

考虑将其写为形式幂级数的形式。

因此

XI

显然答案为 。

XII

显然答案为 。