装球的袋子题解

思路

记奇数编号球的数量为 $o=\lceil m/2\rceil$，偶数编号球数量为 $e=\lfloor m/2\rfloor$。恰有 $f$ 个袋子取到奇数球的方案数为

$$\binom nf o^f e^{n-f}.$$

因此中规模可以直接枚举 $f=0,1,\ldots,n$，累加 $f^k$ 乘以上式，复杂度为 $O(n)$。

小规模则可以枚举每个袋子选择的具体编号，直接统计 $F$。

为了摆脱对巨大 $n$ 的枚举，使用第二类斯特林数恒等式

$$F^k=\sum_{i=0}^k S(k,i)F^{\underline i},$$

其中 $F^{\underline i}=F(F-1)\cdots(F-i+1)$。

做法

对固定的 $i$，$F^{\underline i}$ 等价于从取到奇数球的袋子中有序选择 $i$ 个。先选这 $i$ 个互异袋子，有 $n^{\underline i}$ 种；这些袋子各有 $o$ 种奇数球选择，其余袋子各有 $m$ 种选择。因此

$$\sum F^{\underline i}=n^{\underline i}o^i m^{n-i}.$$

最终答案为

$$\sum_{i=1}^k S(k,i)n^{\underline i}o^i m^{n-i}.$$

预处理所有 $S(k,i)$：

$$S(k,i)=S(k-1,i-1)+iS(k-1,i).$$

每个测试用例从 $i=1$ 到 $k$ 递推下降幂、$o^i$ 与 $m^{n-i}$。由于 $1\le m<998244353$，可用 $m$ 的模逆逐步更新最后一项。

复杂度

一次性预处理复杂度为 $O(K^2)$、空间复杂度为 $O(K^2)$，其中 $K=2000$。每个测试用例时间复杂度为 $O(k+\log n)$。