传送门

多项式多点插值+多点求值的模板题。

不过之前一直以为插值是$O(n\log^3n)$的,直到这题solution给了一个两个log的做法。插值的瓶颈在于求出$g_i=\prod_{i\ne j}(x_i-x_j)$,我们可以把他表示成$f(x)=\frac{\prod{x-x_j}}{x-x_i}$在$x=x_i$处的极限。根据洛必达法则,我们对分式上下求导,得到$\lim_{x\to x_i}f(x)=(\prod(x-x_j))'|_{x=x_i}$。也就是说,我们先分治算出$\prod(x-x_j)$,然后再把这个多项式求导,并在所有$x_i$处多点求值一下,就能得到所有的$g_i$。得到$g_i$之后就好办了,代到拉格朗日插值的式子里面,随便分治一下就出来了。

好久没写这种东西了,代码写的很乱。。。感觉要调整一下写法了。

#include <bits/stdc++.h>
#define LL long long
#define MAXN 270000
#define MAXW 262144
#define B 600
using namespace std;

const LL P=998244353;
LL w[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct Poly{
    LL a[MAXN];
    int len;
    inline LL &operator[](int i){ return a[i]; }
    void reset(int _len){ len=_len; memset(a,0,(len+1)*sizeof(LL)); }
};

void FFT(Poly &a,int len,int flag){
    static int rev[MAXN],revlen;
    if(revlen!=len){
        revlen=len;
        for(int i=1;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    }
    for(int i=0;i<len;i++) if(i<rev[i]) swap(a.a[i],a.a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            for(int j=0;j<l2;j++){
                LL t1=a.a[i+j],t2=a.a[i+j+l2]*w[MAXW/l*j];
                a.a[i+j]=(t1+t2)%P;
                a.a[i+j+l2]=(t1-t2)%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a.a[i]=a.a[i]*invn%P;
        for(int i=1;i<len;i++) if(i<len-i) swap(a.a[i],a.a[len-i]);
    }
}

void getMul(Poly &a,Poly &b,Poly &c){
    int sizew=1;
    while(sizew<=a.len+b.len) sizew<<=1;
    sizew<<=1;
    static Poly t1,t2;
    t1.reset(sizew); t2.reset(sizew);
    for(int i=0;i<=a.len;i++) t1[i]=a[i];
    for(int i=0;i<=b.len;i++) t2[i]=b[i];
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,sizew,-1);
    c.len=a.len+b.len;
    for(int i=0;i<=c.len;i++) c[i]=t1[i];
}

void getInv(Poly &b,Poly &a,int len=-1){
    if(len==-1) for(len=1;len<=a.len;len<<=1);
    if(len==1){
        b.len=len;
        b[0]=getPow(a[0],P-2);
        return;
    }
    static Poly t1,t2;
    getInv(t1,a,len>>1);
    for(int i=len>>1;i<len<<1;i++) t1[i]=0;
    t2.reset((len<<1)-1);
    for(int i=0;i<len;i++) t2[i]=a[i];
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=(2*t1[i]-t2[i]*t1[i]%P*t1[i])%P;
    FFT(t1,len<<1,-1);
    b.len=len-1;
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void reverse(Poly &a){
    for(int i=0;i<=a.len;i++) if(i<a.len-i) swap(a[i],a[a.len-i]);
}

void getMod(Poly &a,Poly &b,Poly &c){
    if(a.len<b.len){
        c.len=a.len;
        for(int i=0;i<=a.len;i++) c[i]=a[i];
        return;
    }
    static Poly t1,t2,t3,t4;
    t1.len=a.len; for(int i=0;i<=a.len;i++) t1[i]=a[i];
    t2.len=b.len; for(int i=0;i<=b.len;i++) t2[i]=b[i];
    reverse(t1); reverse(t2);
    while(t2.len<a.len-b.len) t2[++t2.len]=0;
    t2.len=a.len-b.len;
    getInv(t4,t2);
    while(t1.len<a.len-b.len) t1[++t1.len]=0;
    while(t4.len<a.len-b.len) t4[++t4.len]=0;
    t1.len=t4.len=a.len-b.len;
    getMul(t1,t4,t3); t3.len=a.len-b.len;
    t2.len=b.len; getMul(t3,t2,t2);
    int lenc=b.len-1;
    c.len=a.len;
    for(int i=0;i<=a.len;i++) c[i]=t1[i]-t2[i];
    reverse(c);
    c.len=lenc;
}

LL *xp[MAXN],*fp[MAXN];

void getXP(int id,LL *x,int len){
    if(len==1){
        xp[id]=new LL[2];
        xp[id][0]=-x[0];
        xp[id][1]=1;
        fp[id]=new LL[2];
        return;
    }
    int mid=len>>1;
    getXP(id<<1,x,mid);
    getXP(id<<1|1,x+mid,len-mid);
    static Poly t1,t2;
    t1.len=mid; t2.len=len-mid;
    for(int i=0;i<=mid;i++) t1[i]=xp[id<<1][i];
    for(int i=0;i<=len-mid;i++) t2[i]=xp[id<<1|1][i];
    getMul(t1,t2,t1);
    xp[id]=new LL[len+1];
    fp[id]=new LL[len+1];
    for(int i=0;i<=len;i++) xp[id][i]=t1[i];
}

void getV(int id,LL *x,LL *y,int len){
    if(len<=B){
        for(int i=0;i<len;i++){
            LL res=0,temp=1;
            for(int j=0;j<=len;j++)
                res=(res+temp*fp[id][j])%P,temp=temp*x[i]%P;
            y[i]=res;
        }
        return;
    }
    int mid=len>>1;
    static Poly tp,t1,t2;
    t1.len=len;
    for(int i=0;i<=len;i++) t1[i]=fp[id][i];
    tp.len=mid;
    for(int i=0;i<=tp.len;i++) tp[i]=xp[id<<1][i];
    getMod(t1,tp,t2);
    for(int i=0;i<=mid;i++) fp[id<<1][i]=t2[i];
    tp.len=len-mid;
    for(int i=0;i<=tp.len;i++) tp[i]=xp[id<<1|1][i];
    getMod(t1,tp,t2);
    for(int i=0;i<=mid;i++) fp[id<<1|1][i]=t2[i];
    getV(id<<1,x,y,mid);
    getV(id<<1|1,x+mid,y+mid,len-mid);
}

void getV(Poly &a,LL *x,LL *y,int len){
    getXP(1,x,len);
    static Poly t1;
    t1.len=len;
    for(int i=0;i<=len;i++) t1[i]=xp[1][i];
    getMod(a,t1,t1);
    for(int i=0;i<=t1.len;i++) fp[1][i]=t1[i];
    for(int i=t1.len+1;i<=len;i++) fp[1][i]=0;
    getV(1,x,y,len);
}

void getPoly(int id,LL *x,LL *y,int len){
    if(len<=B){
        for(int i=0;i<=len;i++) fp[id][i]=0;
        for(int i=0;i<len;i++){
            LL last=0;
            for(int j=len;j;j--){
                LL temp=(xp[id][j]+last)%P;
                last=temp*x[i]%P;
                fp[id][j-1]=(fp[id][j-1]+temp*y[i])%P;
            }
        }
        return;
    }
    int mid=len>>1;
    getPoly(id<<1,x,y,mid);
    getPoly(id<<1|1,x+mid,y+mid,len-mid);
    static Poly t1,t2;
    t1.len=mid; for(int i=0;i<=t1.len;i++) t1[i]=fp[id<<1][i];
    t2.len=len-mid; for(int i=0;i<=t2.len;i++) t2[i]=xp[id<<1|1][i];
    getMul(t1,t2,t1);
    for(int i=0;i<=len;i++) fp[id][i]=t1[i];
    t1.len=len-mid; for(int i=0;i<=t1.len;i++) t1[i]=fp[id<<1|1][i];
    t2.len=mid; for(int i=0;i<=t2.len;i++) t2[i]=xp[id<<1][i];
    getMul(t1,t2,t1);
    for(int i=0;i<=len;i++) fp[id][i]=(fp[id][i]+t1[i])%P;
}

void getPoly(LL *x,LL *y,Poly &f,int len){
    getXP(1,x,len);
    static Poly py;
    static LL yv[MAXN];
    py.len=len;
    for(int i=0;i<=len;i++) py[i]=xp[1][i];
    for(int i=0;i<len;i++) fp[1][i]=py[i+1]*(i+1)%P;
    fp[1][len]=0;
    getV(1,x,yv,len);
    for(int i=0;i<len;i++) yv[i]=y[i]*getPow(yv[i],P-2)%P;
    getPoly(1,x,yv,len);
    for(int i=0;i<=len;i++) f[i]=fp[1][i];
    f.len=len;
}

void init(){
    w[1]=getPow(3,(P-1)/MAXW);
    w[0]=1;
    for(int i=2;i<MAXW;i++) w[i]=w[i-1]*w[1]%P;
}

void gao(){
    int n,m;
    static LL xv[MAXN],yv[MAXN];
    static Poly f;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld%lld",xv+i,yv+i);
    getPoly(xv,yv,f,n);
    scanf("%d",&m);
    for(int i=0;i<m;i++) scanf("%lld",xv+i);
    getV(f,xv,yv,m);
    for(int i=0;i<m;i++) printf("%lld ",(yv[i]%P+P)%P);
}

int main(){
#ifdef DEBUG
    freopen("120.in","r",stdin);
#endif
    init();
    gao();
}