.png)
之前一直没有认真学习过拉格朗日插值，今天做题用到了，专门学了学。
如果有错误求指正 awa。
求值
注意区分 x_i 和 x 的含义，我最开始没有区分导致一直不理解（唐），把多项式写成了大写，这样好区分（虽然我并不知道这样写对不对）。
首先是拉格朗日插值最基本的式子是怎么推出来的。
有系数 f_i(x) 满足当 x = x_i 时，其值为 1 否则为 0。
构造得到
f_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}
然后就能得到
F(x) = \sum_{i = 1}^n y_i f_i(x)
也就是
F(x) = \sum_{i = 1}^n y_i \prod_{j \neq i}\frac{x - x_j}{x_i - x_j}
一个 n 次多项式，只需要 n + 1 个点值即可确定，于是求出点值之后带入即可，时间复杂度 O(n^2)。
优化 DP 的例题：P4463 [集训队互测 2012] calc
求系数
首先可以直接 O(n^3) 求，好像（？），没细想，aqz 大佬说可以。
如何优化到 O(n^2)？
有一些值是重复计算过的，于是可以提前求出来它。
设 G(x) = \prod_{i = 1}^n (x - x_i)，原式可以变为
F(x) = \sum_{i = 1}^n y_i \frac{G(x)}{x - x_i} \prod_{j \neq i} \frac{1}{x_i - x_j}
可以 O(n^2) 预处理出来 G(x)，然后可以 O(n) 枚举 i，O(n) 把 G(x) 除以 x - x_i，然后 O(n) 求得 \prod_{j \neq i} \frac{1}{x_i - x_j}，严格控制在 O(n^2) 丝毫没有浪费 orz。
优化 DP 的例题：P10221 [省选联考 2024] 重塑时光（没见到比较板的，目前就见过这一个）