拉格朗日插值法

参考资料

简介

插值

在离散数据的底子上补插连续的函数，使得这条连续函数经过所有离散数据点，这个过程就叫插值。
其意义在于：
插值是离散函数迫近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。
拉格朗日插值法

其核心思想在于直接硬性配凑，先分成差别的子函数，在合并成一个新的函数，很多时间只需要知道 \(O\)。
引入

模板题

给定 \(n\) 个点 \((x_i, y_i)\)，满足所有 \(x_i\) 互不相同，则存在唯一次数不超过 \(n-1\) 的多项式 \(y=f(x)\) 经过这些点。要求确定该多项式并计算 \(f(k) \bmod 998244353\)。
\(n \le 2\times 10^3,\ 1 \le x_i, y_i, k < 998244353\)，\(x_i\) 两两差别。
解法

底子

我们对每个点构造一个子函数，令其只在该点取值为 1，否则为 0。
也就是说，我们要计算 $ n $ 个子函数，第 $ i $ 个子函数为：

\[f_i(x) =\begin{cases} 1 & x = x_i \\0 & x = x_j (j \neq i) \\Who \ \ cares & \text{otherwise}\end{cases}\]
那么插值的结果就是：

\[f(x) = \sum_{i=1}^n y_i f_i(x)\]
对于一样平常情势：对于 $ n $ 个点 \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\) (\(x_1 < x_2 < \cdots < x_n\))，设：

\[f_i(x) = \frac{\prod_{j \neq i}(x - x_j)}{\prod_{j \neq i}(x_i - x_j)}\]
那么插值结果就是：

\[f(k) = \sum_{i=1}^n y_i f_i(k) = \sum_{i=1}^n y_i \times \frac{\prod_{j \neq i}(k - x_j)}{\prod_{j \neq i}(x_i - x_j)}\]
直接算上面这个求和式子就可以得到 \(O(n^2)\) 的做法，我们可以通过一些小小的变形变成 \(O(n^2)\) 预处理 \(O(n)\) 查询，具体看重心拉格朗日差值。
   code [code]ll ans=0;for(int i=1;i