不知道叫什么好，就先这个名字吧，随机写一点。
拉格朗日插值
叫寺院 拉格朗日插值
定义 & 构造
已知 \(n+1\) 个点可以唯一确定一个 \(n\) 次多项式，记多项式 \(f(x) = \sum \limits_{i=0}^n f_ix^i\)，有其 \(n+1\) 个点权 \(f(x_i) = y_i\)，拉插就可以求出其任意位置的值。
记当前求值为 \(X\)，要求出 \(f(X)\)，仿照 crt 的构造，我们构造 \(g_i(x_j) = [i=j]\)，那么显然有一种合法构造：
\[g_i(x) = \prod \limits_{i \neq j} \frac{X-x_j}{x_i-x_j}
\]
那么 \(f(X) = \sum y_ig_i(X)\)，暴力计算是 \(O(n^2)\) 的。
取值连续时的优化
很多情况下，我们可以取到 \(n+1\) 个连续的点值，即 \(x_i = i\)，那么我们就可以更新一下式子了：
\[g_i(x) = \prod \limits_{i\neq j} \frac{x-j}{i-j} = \prod \limits_{j=1}^{i-1} \frac{x-j}{i-j} \prod \limits_{j=i+1}^n \frac{x-j}{i-j} = \frac{1}{(i-1)!} \prod \limits_{j=1}^{i-1} (x-j) \frac{(-1)^{n-i+1}}{(n-i+1)!} \prod \limits_{j=i+1}^{n} (x-j)
\]
这个式子的所有东西都可以 \(O(n)\) 预处理了，单次插值 \(O(n)\)。
优化 dp
拉插最常用的 trick 了吧，一般可以用于优化与值域强相关的 dp，比如树上背包，如果用多项式表示 dp 转移的话，如果 dp 的状态数比多项式的最终次数大的多，我们就可以用多项式次数个点表示整个 dp 的转移，进而优化转移。
主要难点在于分析多项式次数和想到拉插吧。
P4781 【模板】拉格朗日插值
板子。
\(\text{Submission}\)
CF622F The Sum of the k-th Powers
给定 \(n,k\)，求 \(\sum \limits_{i=1}^n i^k\)。
\(1 \le n \le 10^9,1 \le k \le 10^6\)。
题目描述都给了 \(n=1,2\) 的情况，猜测自然数幂和是一个 \(k+1\) 次多项式，取 \(k+1\) 个连续点值插值就好了，复杂度 \(O(k)\)。
\(\text{Submission}\)