【codechef】【May Challenge 2019 Division 2】【Trees and Degrees】题解

[题目链接](https://www.codechef.com/MAY19B/problems/TREDEG) ### 题目描述 给定 $n,k$，若随机生成一棵带标号的树，求所有点的度数的 $k$ 次方的乘积的期望值 有 $50\%$ 的数据保证 $k=1,\sum n \le 2 \times 10^6$ 有另外 $50\%$ 的数据保证 $1 \le k \le 10^9, \sum n \le 100000$ ### 题解 很无聊的二合一…… 显然就搬到 `prufer 序列` 上做就行了，设： $$F(x)=\sum_{n \ge 0}\frac{n+1}{n!}x^n$$ 然后跑个多项式快速幂就有 $50$ 分了 考虑 $k=1$，有： $$F^n(x)=\left(\left( \sum_{n \ge 1} \frac{1}{(n-1)!}x^n \right) + \left( \sum_{n \ge 0} \frac{1}{n!}x^n \right) \right)^n = \left(xe^{x}+e^{x}\right)^n =e^{nx} (x+1)^n$$ 由于： $$\begin{cases}e^{nx}=\sum_{k \ge 0} \frac{n^k}{k!}x^k \\(x+1)^n=\sum_{k \ge 0} {n \choose k}x^k\end{cases}$$ 所以： $$[x^m]e^{nx}(x+1)^n=\sum_{i+j=m} \frac{n^i}{i!} {n \choose j}$$ 单次暴力枚举 $i$，然后 $j=m-i$，直接计算就行了，其中 $m=n-2$