拉格朗日插值只插出多项式

· · 题解

好像题解里都是直接带进去求值了，没有把系数插出来的，那蒟蒻就放一个不开O2跑不过的插系数的拉格朗日插值吧

仍然是拉格朗日基本多项式乘上每个y之后求和

F(x)=\sum\limits_{i=1}^n(y_i\prod_{i!=j} \frac{x-x_j}{x_i-x_j})

观察一下，对于每个i，我们把式子拆成两部分，第一部分是

y_i\prod_{i!=j}\frac{1}{x_i-x_j}

这个东西对于每个i都可以现场O(n)求出来

第二部分是比较棘手的

\prod_{i!=j}(x-x_j)

如果我们对每个i都直接暴力求的话求一次就要O(n^2)，总复杂度O(n^3) (不如高斯消元)

这里需要我们预处理，即先O(n^2)预处理出

\prod\limits_{i=1}^n(x-x_i)

然后考虑背包的思想，我们对于每个i单独扣掉那个x-x_i即可。现在我们已知F'(x)=F(x)(x-x_i)，要求出F(x)。做法是从低次向高次依次还原，脚动模拟多项式除法。就是说(下面用F(x)_j表示F(x)的j次项的系数)

F(x)_j=-(F'(x)_j-F(x)_{j-1})/x_i,F(x)_0=-F'(x)_0/x_i

最后把对于每个i求出来的多项式求个和就可以了，因为取模过多等原因跑的非常慢，不开O2只得80pts，虽然理论复杂度是和直接插出值来的做法一样的=。=

Upd on 2019.3.27：

省选前复习的时候看到了自己写的题解，发现自己原来写的时候沙茶了，居然每次都现场求逆元。。。。。。先预处理逆元就没事了

感谢@xzy_test的提醒

#include<cstdio>
#include<cstring>
#include<algorithm>
#define O 1ll
using namespace std;
const int N=2005,mod=998244353;
int n,k,x[N],y[N],num[N],tmp[N],res[N],inv[N];
void Add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
void exGCD(int a,int b,int &x,int &y)
{
    if(!b) x=1,y=0;
    else exGCD(b,a%b,y,x),y-=a/b*x;
}
int Inv(int x)
{
    int xx,yy;
    exGCD(x,mod,xx,yy);
    Add(xx,mod); return xx;
}
void Lagrange()
{
    for(int i=1;i<=n;i++)
    {
        int den=1,lst=0;
        for(int j=1;j<=n;j++)
            if(i!=j) den=O*den*(x[i]-x[j]+mod)%mod;
        den=O*y[i]*Inv(den)%mod;
        for(int j=0;j<n;j++)
        {
            tmp[j]=O*(num[j]-lst+mod)*inv[i]%mod;
            Add(res[j],O*den*tmp[j]%mod),lst=tmp[j];
        }
    }
}
void Pre()
{
    num[0]=1;
    for(int i=1;i<=n;swap(num,tmp),i++)
    {
        tmp[0]=0; inv[i]=Inv(mod-x[i]);
        for(int j=1;j<=i;j++) tmp[j]=num[j-1];
        for(int j=0;j<=i;j++) Add(tmp[j],O*num[j]*(mod-x[i])%mod);
    }
}
int Calc(int x)
{
    int ret=0,var=1;
    for(int i=0;i<n;var=O*var*x%mod,i++)
        Add(ret,O*var*res[i]%mod);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    Pre(),Lagrange(),printf("%d",Calc(k));
    return 0;
}