拉格朗日插值

给出个点，将过这个点的最多次的多项式记为，求的值。

方法 1：差分法¶

差分法适用于的情况。

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

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

方法 2：待定系数法¶

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

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

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

方法 3：拉格朗日插值法¶

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

那么我们会有：

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

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

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

则模意义下的逆元就是：

所以就有：

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

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

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

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

代码实现¶

#include <cstdio>

const int maxn = 2010;
using ll = long long;
ll mod = 998244353;
ll n, k, x[maxn], y[maxn], ans, s1, s2;

ll powmod(ll x, ll n) {
  ll ret = 1ll;
  while (n) {
    if (n & 1) ret = ret * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}

ll inv(ll x) { return powmod(x, mod - 2); }

int main() {
  scanf("%lld%lld", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%lld%lld", x + i, y + i);
  for (int i = 1; i <= n; i++) {
    s1 = y[i] % mod;
    s2 = 1ll;
    for (int j = 1; j <= n; j++)
      if (i != j) s1 = s1 * (k - x[j]) % mod, s2 = s2 * (x[i] - x[j]) % mod;
    ans += s1 * inv(s2) % mod;
  }
  printf("%lld\n", (ans % mod + mod) % mod);
  return 0;
}

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article Ir1d, Marcythm, YanWQ-monad, x4Cx58x54
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

拉格朗日插值

方法 1：差分法¶

方法 2：待定系数法¶

方法 3：拉格朗日插值法¶

代码实现¶

Comments