Product Trick 初体验

这个题式子可以非常简单，刚好也用这个题试验一下以前都没用过的 product trick。

观察式子，$|S|\times\sum_{x\in S}w_x$ 可以类比为 $|S|\times |S|$，后者是在集合中有序可重选择两个东西的方案数。那么前者的式子显然为“在集合中有序可重选择两个东西，其中第一个贡献为 $1$，第二个贡献为 $w_x$，贡献乘积和”。

回到原题。我们要把这个大集合分成 $k$ 个小的，那么我们拆贡献，钦定一个点 $x$ 为选择的第二个数（贡献乘 $w_x$），那么这个钦定对答案带来的贡献就是“$\sum_{y}1\times w_x\times ways(x,y)$”，其中 $1$ 表示钦定 $y$ 为第一个数，贡献乘 $1$；$ways(x,y)$ 表示分集合使得 $x,y$ 在一个集合（不然没有 $1\times w_x$ 的贡献方法）的方案数。提出 $w_x$ 项，那么问题转为快速计算 $R=\sum_{y=1}^nways(x,y)$。

不难发现，$ways(x,y_1)=ways(x,y_2)$，当 $y_1\ne x,y_2\ne x$ 的时候。$x\ne y$ 时 $ways(x,y)$ 相当于把 $x$ 和 $y$ 绑到一起，就是 $(n-1)$ 个物品放到 $k$ 个非空子集，显然贡献为第二类斯特林数 $S(n-1,k)$；而 $x=y$ 时贡献就是 $S(n,k)$，每一种分法这个贡献一定是有的（自己和自己一定在一个集合）。

总结一下，$R=\sum_{y=1}^n ways(x,y)=S(n,k)+\sum_{y\ne x}S(n-1,k)=S(n,k)+(n-1)\times S(n-1,k)$。故答案为 $\sum_{i=1}^n a_iR$。

复杂度是计算单个斯特林数的 $\Theta(n\log n)$。

NOIP 2025 RP++