拉格朗日插值法

$n+1$个点可以唯一确定一个$n$次的多项式
当然可以用高斯消元解，但复杂度是$O\left ( n^{3} \right )$的
这里引入拉格朗日插值法

拉格朗日插值法

对于$x_{i}$，假设有多项式$\ell_{i}$

$$\ell_{i}\left ( x \right )=\left\{\begin{matrix} 1 \ \left ( x=x_{i} \right ) \\ 0 \ \left ( x\neq x_{i} \right ) \end{matrix}\right.$$

则

$$y_{i}\ell_{i}\left ( x \right )=\left\{\begin{matrix} y_{i} \ \left ( x=x_{i} \right ) \\ 0 \ \left ( x\neq x_{i} \right ) \end{matrix}\right.$$

不难得出

$$\forall k\leq n+1 ,\sum_{i=1}^{n+1} y_{i}\ell_{i}\left ( x_{k} \right )=y_{k}$$

即该多项式经过所有$n+1$个点

考虑如何构造$\ell_{i}\left ( x \right )$
显然如下构造可行

$$\ell_{i}\left ( x \right )=\prod _{i\neq j}\frac{\left ( x-x_{j} \right )}{\left ( x_{i}-x_{j} \right )}$$

对于每个$x_{j}\left ( i\neq j \right )$，分子中都会出现$0$
而将$x_{i}$带入时，分子分母完全相同

化简可得

$$f\left (x \right )=\sum_{i=1}^{n+1}y_i\prod_{j\neq i}\frac{\left ( x-x_{j} \right )}{\left (x_{i}-x_{j} \right )}$$

单次求值复杂度$O\left ( n^{2} \right )$

重心拉格朗日插值法

不难发现$\ell_{i}\left ( x \right )$有重复计算部分
设

$$\ell\left ( x \right )=\prod_{i=1}^{n+1} \left ( x-x_{i} \right )$$ $$w_{i}=\frac{1}{\prod _{i\neq j}\left ( x_{i}-x_{j} \right )}$$

不难得到

$$\ell_{i}\left ( x \right )=\ell\left ( x \right )\frac{w_{i}}{x-x_{i}}$$

化简可得

$$f\left (x \right )=\ell\left ( x \right )\sum _{i=1}^{n+1}y_{i}\frac{w_{i}}{x-x_{i}}$$

单次求值复杂度还是$O\left ( n^{2} \right )$
当动态加入点时，一般拉格朗日插值法需要$O\left ( n^{2} \right )$重新计算，而重心拉格朗日插值法只需$O\left ( n \right )$计算一遍$w_{i}$

#include<cstdio>
#define LL long long
const int mod=998244353;
const int N=2050;
LL n,x,a[N],b[N],ans=0;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
LL pow(LL a,LL b,LL mod)
{
    LL ret=1;
    for(;b;b>>=1)
    {
        if (b&1) ret=ret*a%mod;
        a=a*a%mod; 
    }
    return ret;
}
int main()
{
    n=read(),x=read();
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
    for(int i=1;i<=n;i++)
    {
        LL A=b[i],B=1;
        for(int j=1;j<=n;j++) if (i!=j)
        {
            A=A*(x-a[j])%mod;
            B=B*(a[i]-a[j])%mod;
        }
        ans=(ans+A*pow(B,mod-2,mod))%mod;
    }
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}