给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法，名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

为了方便理解，我们把上面那个式子等价地拆成两部分

$$ \ell_j(x)=\prod_{i=1,i \ne j}^{n}{\frac{x-x_i}{x_j-x_i}} $$

$$ P(x)=\sum_{i=1}^{n}y_i\ell_i(x) $$

先让我们看看第一个式子

$$ \ell_j(x)=\prod_{i=1,i \ne j}^{n}{\frac{x-x_i}{x_j-x_i}} $$

这个式子有一个性质

当`x=x_i`时$$ \ell_j (x) = 0 $$

当`x=x_j`时$$ \ell_j (x) = 1 $$

这时候我们想起第二个式子

$$ P(x)=\sum_{i=1}^{n}y_i\ell_i(x) $$

不难发现，当我们在代入第`i`个坐标时，除第`i`个分式外，所有分式的的值等于0

而代入第`i`个坐标后，分子分母完全相当，约去后只剩一下个`y_i`

说到这里想必有点难以理解，让我们来看一个例子

代入的三个点为`(1,4),(2,9),(3,16)`

$$ f(x) = 4\frac{(x-2)(x-3)}{(1-2)(1-3)} + 9\frac{(x-1)(x-3)}{(2-1)(2-3)} + 16\frac{(x-1)(x-2)}{(3-1)(3-2)} $$

代入后`f(x)=x^2+2x+1`

代码

#include <stdio.h>
#include <algorithm>

typedef long long LL;

const int N = 2e3;
const LL P = 998244353;

LL n, k, ans;
LL x[N + 5], y[N + 5];

LL pow(LL x, LL k)
{
    LL res = 1;
    while (k)
    {
        if (k & 1)
            res = res * x % P;
        x = x * x % P;
        k >>= 1;
    }
    return res;
}

void Lagrange_Interpolation()
{
    for (int i = 1; i <= n; i++)
    {
        LL a = 1, b = 1;
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            a = a * (k - x[j]) % P;
            b = b * (x[i] - x[j]) % P;
        }
        ans = (ans + a * pow(b, P - 2) % P * y[i]) % P;
    }
    ans = (ans + P) % P;
}

int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &x[i], &y[i]);
    Lagrange_Interpolation();
    printf("%lld", ans);
    return 0;
}

参考文献