拉格朗日插值

方法 1：差分法

差分法适用于 的情况。

如，用差分法求某三次多项式 的多项式形式，已知 至 的值分别为 。

第一行为 的连续的前 项；之后的每一行为之前一行中对应的相邻两项之差。观察到，如果这样操作的次数足够多（前提是 为多项式），最终总会返回一个定值，可以利用这个定值求出 的每一项的系数，然后即可将 代入多项式中求解。上例中可求出 。时间复杂度为 。这种方法对给出的点的限制性较强。

方法 2：待定系数法

设 将每个 代入 ，有 ，这样就可以得到一个由 条 元一次方程所组成的方程组，然后使用 高斯消元 解该方程组求出每一项 ，即确定了 的表达式。

如果您不知道什么是高斯消元，请看

高斯消元。

时间复杂度 ，对给出点的坐标无要求。

方法 3：拉格朗日插值法

在

多项式部分简介 里我们已经定义了多项式除法。

那么我们会有：

这是显然的，因为 ，这个式子显然有 这个因式，所以得证。

这样我们就可以列一个关于 的多项式线性同余方程组：

我们根据中国剩余定理，有：

则 模 意义下的逆元就是：

所以就有：

所以在模意义下 就是唯一的，即：

这就是拉格朗日插值的表达式。

如果要将每一项的系数都算出来，时间复杂度仍为 ，但是本题中只用求出 的值，所以在计算上式的过程中直接将 代入即可。

本题中，还需要求解逆元。如果先分别计算出分子和分母，再将分子乘进分母的逆元，累加进最后的答案，时间复杂度的瓶颈就不会在求逆元上，时间复杂度为 。

代码实现

横坐标是连续整数的拉格朗日插值

如果已知点的横坐标是连续整数，我们可以做到 插值。

设要求 次多项式为 ，我们已知 （），考虑代入上面的插值公式：

后面的累乘可以分子分母分别考虑，不难得到分子为：

分母的 累乘可以拆成两段阶乘来算：

于是横坐标为 的插值公式：

预处理 前后缀积、阶乘阶乘逆，然后代入这个式子，复杂度为 。

本题中，答案是一个 次多项式，因此我们可以线性筛出 的值然后进行 插值。