回到原题。我们要把这个大集合分成 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)，每一种分法这个贡献一定是有的（自己和自己一定在一个集合）。