非常组合数学。

先考虑暴力 DP，因为 表示选了前 个数，一共选了 个的权值和。那么 。

注意到转移式里带个 的系数非常斯特林数，考虑把它凑出来，令 ，转移式变成：

。

那么就可以考虑组合意义了，以 的系数新开一个集合，以 的系数放入已有的一个集合，以 的系数不放入任何一个集合。

设 。

那么枚举有 个元素不放入任何一个集合，那么剩下 个元素的方案数就是 。而 数组的 EGF 就是 ，容易求出。那 个元素的贡献之和就是 。用分治 + FFT 求出来即可。

总时间复杂度。