LuoGu: CF622F The Sum of the k-th Powers
CF: F. The Sum of the k-th Powers
直接想到伯努利数，但是伯努利数直接求复杂度是 $O(m ^ 2)$ 。考虑插值，当取连续的 $x _ i = i$ 时，可以实现线性插值。即
$$
\begin{aligned}
f(x) = & \sum_{i = 1}^n f(i) \prod_{j \ne i}\frac{(x - j)}{(i - j)} \\
= & \sum_{i = 1}^n f(i) * (-1)^{n - i} * \frac{\prod _ {k \neq i} (x - k)}{(i - 1)!(n - i)!} \\
\end{aligned}
$$
维护出 $\sum _ k (x - k)$ 。每次计算时乘上对应逆元。注意到如果 $n \le m + 2$ ，那么答案为 $0$ 。这部分暴力计算即可。
查看代码
1 |