拉格朗日插值·模板

首先我们考虑我们有 $n$ 个点值表达式。

$$\begin{Bmatrix}(x_1,y_1),(x_1,y_1)\cdots(x_n,y_n)\end{Bmatrix}$$

我们想构造 $\forall i\in [0,n]\ \ \ F(x_i)=y_i$。

$$F(x)=\sum _{i=0}^{n}y_i\times f_i(x)$$

$f_i(x)$满足 $\forall j\not ={i} f_i(x_j)=0$,$f_i(x_i)=1$。
所以构造多项式。

$$f_i(x)=\prod_{j=0,j\not ={i}}^{n}\frac{x-x_j}{x_i-x_j}=\frac{x-x_0}{x_i-x_0}\cdots\frac{x-x_{i-1}}{x_i-x_{i-1}}\frac{x-x_{i+1}}{x_i-x_{i+1}}\cdots \frac{x-x_n}{x_i-x_n}$$

分析：

1. 当 $x=xi$, $f_i(x_i)=\displaystyle\prod{j=0,j\not ={i}}^{n}\frac{x_i-x_j}{x_i-x_j}=\prod 1=1$
2. 当 $x\not =x_i$ 时，设$x=x_k$ 则分子为 $(x_k-x_1)\cdots(x_k-x_k)\cdots (x_k-x_n)=0$ ,$\ \ f_i(x_k)=0$

ok!
就是你啦。

$$F(x)=\sum _{i=0}^{n}y_i\times \prod_{j=0,j\not ={i}}^{n}\frac{x-x_j}{x_i-x_j}$$

#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
#define int long long
inline void read(int &x)
{
    char c=getchar();x=0;int f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    x=x*f;
}
inline int qpow(int a,int b,int p)
{
    int k=1;
    while(b)
    {
        if(b&1) k=k*a%p;
        a=a*a%p,b=b>>1;
    }
    return k;
}
const int N=1e4,p=998244353;
inline int inv(int x){return qpow(x,p-2,p);}
int n,k;
int x[N],y[N],ans,chushu=1;
signed 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++)
    {
        int res=1;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            res=res*(k-x[j])%p*inv(x[i]-x[j])%p;
        }
        ans=ans+res*y[i]%p;
    }
    printf("%lld",ans%p);
}