思路

拉格朗日插值是一种能够根据n个点\((x_i,y_i)\)求出对应多项式的方法

定义拉格朗日插值的基函数\(L(i)\)为

\[ L(i)=\prod_{j=0,j\not=i}^n\frac{x-x_j}{x_i-x_j}y_i \]

容易发现这个函数的特点就是当\(x=x_i\)时，\(y=y_i\)，其他时候\(y=0\)

所以最后插值出来的多项式就是这n个基函数求和（恰好在每个\(x_i\)处取到\(y_i\)）

\[ G(x)=\sum_{i=0}^n L(i) \]

然后没了

还有重心拉格朗日插值之后再说

代码

#include 
    
     #include 
     
      #include 
      
       #define int long longusing namespace std;const int MOD = 998244353;int pow(int a,int b){    int ans=1;    while(b){        if(b&1)            ans=(ans*a)%MOD;        a=(a*a)%MOD;        b>>=1;    }    return ans;}int n,k,x[2020],y[2020];signed main(){    scanf("%d %d",&n,&k);    for(int i=1;i<=n;i++){        scanf("%d %d",&x[i],&y[i]);    }    int ans=0;    for(int i=1;i<=n;i++){        int up=1,down=1;        for(int j=1;j<=n;j++)            if(i!=j){                up=up*(k-x[j]+MOD)%MOD;                down=down*(x[i]-x[j]+MOD)%MOD;            }        ans=(ans+up*y[i]%MOD*pow(down,MOD-2)%MOD+MOD)%MOD;        // printf("%d\n",ans);    }    printf("%d\n",ans);    return 0;}