拉格朗日插值 备忘
拉格朗日插值大概在做一个什么事？
用 \(n\) 个点来表达一个 \(n-1\) 次多项式 \(f\)，然后想要在不把多项式的系数表示法求出来的前提下快速求 \(f(x)\)。
\[L(x)=\sum_{i=1}^n y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} \]时间复杂度每次插值都是 \(O(n^2)\)。
注意点：
分别求分子分母，逆元就不会构成复杂度瓶颈。
横坐标 \(x\) 是连续整数，可以做到 \(O(n)\) 插值。
横坐标为 \(1,2,...,n+1\) 的插值公式：
\[f(x)=\sum_{i=1}^{n+1}y_i\cdot\frac{\prod\limits_{j=1}^{n+1}(x-j)}{(x-i)\cdot(-1)^{n+1-i}\cdot(i-1)!\cdot(n+1-i)!} \]重心拉格朗日插值，这玩意第一次听说，可以 \(O(n^2)\) 预处理，\(O(n)\) 求一次值。
\[f(x)=\sum_{i=1}^ny_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\\ 令 \ g=\prod_{i=1}^n (x-x_i)\\ f(x)=g\sum_{i=1}^n\prod_{j\ne i}\frac{y_i}{(x-x_i)(x_i-x_j)}\\ 令 \ t_i=\frac{y_i}{\prod\limits_{j\ne i}(x_i-x_j)}\\ f(x)=g\sum_{i=1}^n\frac{t_i}{x-x_i} \]所以单次求的复杂度是 \(O(n)\) 的。（大意是变形式子）
拉插可能会出现在优化下标很大的 \(dp\) 中，要发现发现一些 \(dp\) 或者其他计数式子为次数不高的多项式。
证明为多项式的一般思路是归纳。
此外这个模板题还可以用差分法或者待定系数法。
差分法：仅仅适用于 \(x_i=i\) 的情况，不断把 \(x\) 作差分能得到一个定值，从而逆推，细节：link。
待定系数法：把函数系数设出来，列出方程组用高斯消元求解，时间复杂度三方。
标签：拉格朗,frac,插值,sum,备忘,cdot,prod From： https://www.cnblogs.com/hellojim/p/17444313.html