EZ、什么是拉格朗日插值？
众所周知，\(n+1\) 个点可以唯一确定一个 \(n\) 次多项式。
拉格朗日插值法要解决的就是给定 \(n+1\) 个点确定一个多项式 \(f(x)\)，求出在自变量 \(x=k\) 时多项式的取值。
拉格朗日插值法的思想和 CRT 非常像——把每一个维度独立拆开来。
考虑对一个点 \((x_i,y_i)\) 构造一个子函数 \(f_i(x)\)，使得 \(f_i(x_i)=y_i\)，且对于每一个 \(j \neq i\)，使得 \(f_i(x_j)=0\)。
如果你上过奶猫老师的数论课，就会意识到这些子函数和 CRT 的 \(\omega_i\) 的思想是完全一样的！
然后就是怎么算子函数了。不需要 exgcd，不需要神秘科技，就是朴素的 \(O(n^2)\) 做法。
令 \(f_i(x_j)=0\) 是容易的，只要让 \(f_i(x)=\displaystyle{\prod_{j=1}^{n}[j \neq i](x-x_j)}\) 就行了。
那怎么修改使得满足另外一个条件呢？其实很简单，加个系数。
最终的结果就是 \(f_i(x)=\displaystyle{\dfrac{y_i\prod_{j=1}^{n}[j \neq i](x-x_j)}{(x_i-x_j)}}\)。
全部加起来就做完了。多简单。
其实复杂度可以更低，但是太超标了。我不会。哭哭。