题解

思路

记第二类 Stirling 数为 $S(n,k)$，整数 $n$ 拆成不超过 $m$ 个正整数之和的方案数为 $p_m(n)$。十二个答案依次为：

$$m^n, P(m,n), m!S(n,m), \sum_{k\le m}S(n,k), [n\le m], S(n,m),$$$$\binom{n+m-1}{m-1}, \binom mn, \binom{n-1}{m-1}, p_m(n), [n\le m], p_m(n-m).$$

越界的组合数和不存在的拆分均为零。

做法

子任务 1

按定义枚举球到盒的映射、集合划分、弱组合和整数拆分，适用于 $n,m\le8$。

子任务 2

对每个 $k$ 用容斥公式

$$S(n,k)=\frac1{k!}\sum_{i=0}^k(-1)^i\binom ki(k-i)^n$$

分别求值，再用背包递推整数拆分。复杂度 $O(m^2\log n+nm)$。

满分算法

统一使用递推 $S(i,j)=S(i-1,j-1)+jS(i-1,j)$，滚动数组求出第 $n$ 行；整数拆分用完全背包：依次加入大小 $1$ 到 $m$ 的部件。阶乘和逆阶乘用于组合数。

复杂度

满分算法时间 $O(nm)$，空间 $O(n+m)$。

易错点

相同盒子允许空盒时只区分非空块数；第十二问等价于先给每盒一球，再拆分剩余 $n-m$ 个球；所有中间量都要及时取模。