【模板】拉格朗日插值

传送门：

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define re register
const int mod=998244353;
inline void read(int &a)
{
    a=0;
    int d=1;
    char ch;
    while(ch=getchar(),ch>'9'||ch<'0')
        if(ch=='-')
            d=-1;
    a=ch^48;
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+(ch^48);
    a*=d;
}
int x[2005],y[2005];
inline int quickmod(int a,int b)
{
    int res=1;
    int base=a;
    while(b)
    {
        if(b&1)
            res=1ll*res*base%mod;
        base=1ll*base*base%mod;
        b>>=1;
    }
    return res;
}
inline int inv(int x){return quickmod(x,mod-2);}
int main()
{
    int n,k;
    read(n);
    read(k);
    for(re int i=1;i<=n;i++)
        read(x[i]),read(y[i]);
    ll ans=0;
    for(re int i=1;i<=n;i++)
    {
        int s1=y[i]%mod;
        int s2=1;
        for(re int j=1;j<=n;j++)
            if(i!=j)
                s1=1ll*s1*(k-x[j])%mod,s2=1ll*s2*(x[i]-x[j])%mod;
        s1=1ll*s1*inv((s2+mod)%mod)%mod;
        (ans+=s1)%=mod;
        (ans+=mod)%=mod;///不加这句会WA
    }
    printf("%lld",ans);
    return 0;
}