神秘矩阵树

求图的所有生成树边权和 \(k\) 次方之和，\(n,k\le 50\)。

Sol:

展开 \(k\) 次方后会得到 \(\sum {k!\over w_1!w_2!...w_{n-1}!} \prod e_i^{w_i}\) 之类的式子，你发现给每条树边设个生成函数 \(f_i(x)=e^{e_ix}\)，答案就是 \(k![x^k]\prod f_i(x)\),于是你用矩阵树，带 \(1\sim nk+1\) 进去，这部分是 \(O(n^4k)\) 的，应该有办法 \(O(n^3k)\)，但不重要。

之后你会发现求这个多项式第 \(k\) 项，直接高消出多项式是 \(O(n^3k^3)\) 的，不太行。注意到只需要求一项，我们考虑拉插的式子：

计算每个 \(i\) 的贡献，我们预处理出 \(x-i\) 的前后缀积，容易发现算 \(x^k\) 的系数只要 \(O(k)\)，于是可以 \(O(nk^2)\) 的插出第 \(k\) 项了。