前言

我们都知道两点确定一条直线，三个点确定一个二次函数，现在给你$n$个点，让你求出一个$n-1$次函数怎么做。

暴力

直接把每个点看成一个方程，$x^0,x^1\dots x^{n-1}$的系数看成未知数，高斯消元解方程，复杂度为$n^3$

朴素拉格朗日插值

我们构造出函数$l_i(x)$，使得$x$取$x_i$时等于1，$x$取$x_1,x_2\dots x_n$(不包括$x_i$)时为0.
设我们最后要求的函数为$f(x)$

$f(x)=\sum\limits_{i=1}^{n}y_i*l_i(x)$

这步应该显然，接下里我们考虑如何构造$l_i(x)$。

$l_i(x)=\prod\limits_{j=1,j\ne i}^{n}\frac{x-x_j}{x_i-x_j}$

显然是满足上面我们的要求的。
但每次询问都要暴力插值，复杂度为$n^2$

重心拉格朗日插值

我们发现$l_i$的分子是有非常多的重复的。
考虑令

$l(x)=\prod\limits_{j=1}^{n}(x-x_j)$

那么

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

再令

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

我们称$w_i$为重心权，所以这个插值方法也叫做重心拉格朗日插值
最后

$f(x)=\sum\limits_{i=1}^{n}y_i*\frac{l(x)}{x-x_i}*w_i$

这样的话可以做到每次修改一个点后，单次查询的复杂度就降到了$O(n)$

代码

贴上求单点值的代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (2005)
using namespace std;
int n,k,l,ans;
const int P=998244353;
int w[N],x[N],y[N];	 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline int inv(int a){
    return ksm(a,P-2);
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
int main(){
    read(n),read(k);
    for (int i=1;i<=n;i++){
        read(x[i]),read(y[i]);
    } 
    for (int i=1;i<=n;i++){
        w[i]=1;
        for (int j=1;j<=n;j++){
            if (i!=j) w[i]=1ll*w[i]*(x[i]-x[j]+P)%P;
        }
        w[i]=inv(w[i]);
    }
    l=1;
    for (int i=1;i<=n;i++) l=1ll*l*(k-x[i]+P)%P;
    ans=0;
    for (int i=1;i<=n;i++){
        ans=Inc(ans,1ll*l*inv(Inc(k-x[i],P))%P*w[i]%P*y[i]%P);
    }
    printf("%d",ans);
    return 0;
}