问题引入：
有一个\(n+1\)项的多项式\(f(x)\)，给出\(n+1\)个点\((x_i,y_i)\)，求这个多项式。
这里我们直接给出问题的答案：
\[
f(x)=\sum_{i=0}^ny_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
\]
考虑我们带入\(x_k\)，可得：
\[
f(x)=\sum_{i=0}^ny_i\prod_{j\ne i}\frac{x_k-x_j}{x_i-x_j}
\]
注意到\(i\ne k\)的项分子一定有一项为\(0\)，所以：
\[
f(x)=y_k\prod_{j\ne k}\frac{x_k-x_j}{x_k-x_j}=y_k
\]
发现这个多项式是满足条件的，证毕。
至此，我们可以在\(O(n^2)\)的时间内求出\(f(x)\)。
\(x_ i\)连续时的情况：
同样我们把式子抄过来：
\[
f(x)=\sum_{i=0}^ny_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
\]
可以发现分子可以用前缀积来表示，设：
\[
pre_i=\prod_{j=0}^i(x-x_j),suf_i=\prod_{j=i}^n(x-x_j)
\]
由于\(x_i\)连续，分母可以写成阶乘的形式，式子变成：
\[
f(x)=\sum_{i=0}^ny_i\frac{pre_{i-1}\cdot suf_{i+1}}{(-1)^{n-i}i!(n-i)!}
\]
至此，我们可以在\(O(k)\)的时间内算出任意一项。
那么我们可以很方便\(O(k)\)的算出\(\sum_{i=1}^ni^k\)，可以比较容易的证明，这是一个\(k+1\)次的多项式，所以直接插值就好了。
其中\(i\in [0,k+1]\)的取值我们可以线筛然后前缀和，对于每个素数我们暴力的快速幂，由于素数密度，这部分的复杂度是\(O(\dfrac{k}{\ln k} \cdot \log k)=O(k)\)。
习题：[BZOJ5339] [TJOI2018]教科书般的亵渎
\[ \underline{\widehat{\dbinom{\odot_\vee\odot}{{\raise-8pt"}\wr{\raise-8pt"}}}} \]
原文：https://www.cnblogs.com/hbyer/p/10583970.html