对于一个 \(n\) 次多项式 \(f(x) = \sum_{k = 0}^n a_kx^k\)，我们只要知道它在 \(n+1\) 个不同点处的取值，就可以进一步解出它的系数
但使用高斯消元法的时间复杂度是 \({\cal O}(n^3)\) 的，如果我们只是想知道这个多项式在某一点 \(x'\) 处的值，希望有复杂度更优的办法
我们希望有这样一组系数 \(\alpha\)，使得：
\[\begin{cases}
\alpha_0x_0^0+\alpha_1x_1^0+\cdots+\alpha_nx_n^0 = x'^0\\
\alpha_0x_0^1+\alpha_1x_1^1+\cdots+\alpha_nx_n^0 = x'^1\\
\quad\vdots\qquad\quad\vdots\qquad\ddots\qquad\!\vdots\quad=\ \vdots\\
\alpha_0x_0^n+\alpha_1x_1^n+\cdots+\alpha_nx_n^n = x'^n\\
\end{cases}\tag{1}
\]
换句话说：
\[\begin{bmatrix}
x_0^0&x_1^0&\cdots&x_n^0\\
x_0^1&x_1^1&\cdots&x_n^1\\
\vdots&\vdots&\ddots&\vdots\\
x_0^n&x_1^n&\cdots&x_n^n\\
\end{bmatrix}\cdot
\begin{bmatrix}
\alpha_0\\
\alpha_1\\
\vdots\\
\alpha_n
\end{bmatrix}=
\begin{bmatrix}
x'_0\\
x'_1\\
\vdots\\
x'_n
\end{bmatrix}\tag{2}
\]
然后答案就是
\[\sum_{k = 0}^n f(x_k)\alpha_k\tag{3}
\]
这个矩阵十分的特殊，它的行列式叫范德蒙德行列式：
\[\det
\begin{bmatrix}
x_0^0&x_1^0&\cdots&x_n^0\\
x_0^1&x_1^1&\cdots&x_n^1\\
\vdots&\vdots&\ddots&\vdots\\
x_0^n&x_1^n&\cdots&x_n^n\\
\end{bmatrix} = \prod_{0 \le i < j \le n}(x_j-x_i)\tag{4}
\]
于是我们考虑在式 \((2)\) 前后同乘逆矩阵，就有：
\[\alpha_k = \sum_{j = 0}^n\frac{(-1)^{j+k}A_{j,k}}{\det}x'^j\tag{5}
\]
而对范德蒙德行列式第 \(k\) 列展开，是：
\[\sum_{j = 0}^n\frac{(-1)^{j+k}A_{j,k}}{\det}x_k^j
\]
那相当于我们 \(x_k\coloneqq x'\) 之后的到了一个新的范德蒙德行列式展开式，它显然只有包含 \(x_k\) 的项是与原来不同的
于是我们得到：
\[\begin{aligned}
\alpha_k &= \sum_{j = 0}^n\frac{(-1)^{j+k}A_{j,k}}{\det}x'^j\\
&= \frac{\det_k}{\det}\\
&= \frac{\prod_{i \not= k}(x'-x_i)}{\prod_{i \not= k}(x_k-x_i)}
\end{aligned}
\]
故答案为：
\[f(x') = \sum_{k = 0}^nf(x_k)\frac{\prod_{i \not= k}(x'-x_i)}{\prod_{i \not= k}(x_k-x_i)}
\]
时间复杂度为 \({\cal O}(n^2)\)。
