通常的，我们被给到一个函数在一些点上的值，我们可以用高斯消元在 \(O(n^3)\) 的时间复杂度内求出对应的多项式
当我们只被要求求出其中的的一个点时，我们可以使用插值这个工具在 \(O(n^2)\) 的时间复杂度之内求解。
一、拉格朗日插值
1. 算法原理
我们现在的目标是构造一个多项式，使得带入每一个给定的点都能够保证得到的答案一一对应
于是乎，我们有一个初始的想法：
\[
f(x) = \sum_{i=1}^n [x == x_i] y_i\]
好想法！但是我们怎么把 \([x == x_i]\) 转化为多项式呢？
我们想要让只有 \(x == x_i\) 的时候，这个多项式的结果为 \(1\)，\(x == x_j (j\neq i)\) 的时候，这个多项式的结果为 \(0\)，其他数的结果任意，并且多项式的理论次数为 \(0\)
我们经过千辛万苦，构造出如下式子：
\[
\prod_{j\neq i} \frac{x-x_j}{x_i-x_j}\]
如何千辛万苦
我们需要构造函数 \(f_1(x),f_2(x),\dots,f_n(x)\) 使得对于函数 \(f_i(x)\) 过点 (x_i,1) 和所有的 \((x_j,0)\)
我们设 \(f_i(x) = A \prod_{j\neq i} (x-x_j)\)，带入 \((x_i,1)\) 可以得到 \(A = \frac 1 {\prod_{j\neq i} (x_i-x_j)}\)
所以 \(f_i(x) = \prod_{j\neq i} \frac {x-x_j} {\prod_{j\neq i} (x_i-x_j)}\)
我们发现，当 \(x = x_i\) 的时候，这个式子的结果是 \(1\)，而当 \(x = x_j\) 的时候，\(x_j-x_j = 0\)，使得结果是 \(0\)
这样我们就得出了拉差式子：
\[
f(x) = \sum_{i=1}^n y_i \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}\]