luogu P5437 【XR-2】约定
考虑每条边的贡献。所有生成树的边数和为 $n^{n-2} \cdot (n-1)$，原图中的边数为 $\frac{n(n-1)}{2}$，因为原图中每条边在最终的树中出现的概率是相同的，所以某条边出现在生成树中的概率为 $\frac{\frac{n^{n-2} \cdot (n-1)}{\frac{n(n-1)}{2}}}{n^{n-2}} = \frac{2}{n}$。
所以
$\sum_{i=1}^n (2i)^k = 2^k \sum_{i=1}^n i^k$ 可以一次拉格朗日插值求出来。
可以证明 $f(n) = \sum_{i=1}^n \sum_{j=1}^n (i+j)^k$ 是一个关于 $n$ 的 $k+2$ 次多项式。
方法 1：$\sum_{t=0}^k \binom{k}{t} \left(\sum_{i=1}^n i^t\right) \left( \sum_{j=1}^n j^{k-t}\right)$，一个 $t+1$ 次多项式和 $k-t+1$ 次多项式相乘后为 $k+2$ 次多项式，求和后仍为 $k+2$ 次多项式。
方法 2：做差，分析得知 $f(n) - f(n-1)$ 是个 $k+1$ 次多项式。
最后的问题是如何算出 $f(1),f(2),\cdots f(k+3)$。
枚举 $u = i+j$，则合法的 $i$ 必须满足 $1\le i\le n, 1\le u-i \le n$。讨论一下可知
预处理 $i^k$ 的前缀和即可。
BZOJ4559 / luogu P3270 [JLOI2016]成绩比较
考虑求出 $F(x)$ 表示钦定 $x$ 个同学被碾压，此时给所有人赋分使得 B 神的排名符合题意的方案数。
则由二项式反演知答案为 $\sum_{x=K}^N \binom{x}{K}(-1)^{x-K} F(x)$。
可以看出 $\sum_{j=1}^{U_i} j^{N-R_i}(U_i-j)^{R_i-1}$ 是一个关于 $U_i$ 的 $N$ 次多项式，可以用拉格朗日插值算。
总时间复杂度 $O(MN^2)$。
BZOJ2655 / luogu P4463 [集训队互测2012] calc
钦定 $a_1 < a_2 < \cdots < a_n$ 算答案，最后乘上一个 $n!$ 即可。
设 $f_{i,j}$ 表示：考虑了前 $i$ 个数，最大的数为 $j$，所有方案的权值和。
则 $f_{i,j} = \sum_{k<j} f_{i-1,k} \cdot j$。
注意到，如果 $f_{i,j}$ 是个关于 $j$ 的 $p$ 次多项式，则 $f_{i,j} \cdot j$ 是个关于 $j$ 的 $p+1$ 次多项式，$\sum_{k < j} f_{i,k}$ 是个关于 $j$ 的 $p+1$ 次多项式。
所以 $f_{n,j}$ 是个关于 $j$ 的 $2n+1$ 次多项式。
直接 dp + 拉格朗日插值，可以做到 $O(n^2)$。
luogu P5850 calc加强版
考虑答案关于 $n$ 的生成函数
剩下的问题就是对每个 $j$ 算 $\sum_{i=1}^A i^j$：
复杂度 $O(n\log n)$，需要卡常。
所以拉格朗日插值有什么用呢？
BZOJ3453 tyvj 1858 XLkxc
$f(n) = \sum_{i=1}^n i^k$ 是关于 $n$ 的 $k+1$ 次多项式；
所以 $g(n) = \sum_{i=1}^n f(i)$ 是关于 $n$ 的 $k+2$ 次多项式。
注意到 $h(n) = g(a+nd)$ 仍然是关于 $n$ 的 $k+2$ 次多项式。
所以 $p(n) = \sum_{i=0}^n h(n)$ 是关于 $n$ 的 $k+3$ 次多项式。
拉格朗日插值即可，复杂度大约 $O(k^2)$。