题目概述

给出一个多项式 $F(x)$ ，有 $m$ 个询问，每次求 $F(a_i)$ 。

解题报告

将 $F(x)$ 在 $x=a$ 处进行泰勒展开：

$$ F(x)=F(a)+F'(a)(x-a)+{F''(a)(x-a)^2\over 2!}+\cdots\\ F(x)\equiv F(a)(mod\ x-a) $$

所以只需要用多项式取模就可以得到 $F(a_i)$ ，但是不可能对于每个 $a_i$ 都进行多项式取模，复杂度爆炸。

因此我们要想办法让 $F(x)$ 缩减规模，很显然 $(x\ mod\ ab)\ mod\ a=x\ mod\ a$ ，所以可以这样：

$$ P_L(x)=\prod_{i=L}^{mid}(x-a_i),P_R(x)=\prod_{i=mid+1}^{R}(x-a_i)\\ F_L(x)=F(x)\ mod\ P_L(x),F_R(x)=F(x)\ mod\ P_R(x) $$

这样分治下去，处理到 $L=R$ 停止，就可以得到 $F(a_L)$ ，复杂度 $O(nlog_2^2n)$ 。

不过分治的时候是无法同时求出 $P$ 的，我们还需要分治NTT预先处理出 $P$ ，复杂度也是 $O(nlog_2^2n)$ 。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxn=64000,maxt=1<<17,MOD=998244353;

int n,m,a[maxn+5],ans[maxn+5];PN F,P[(maxn<<2)+5];

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
namespace Poly{
    int rev[maxt+5],pw[2][maxt+5],tem[maxt+5];
    inline void Pre(int n){
        for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
        for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
    }
    inline void NTT(int *a,int n,int f){
        for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
        for (int k=1;k<n;k<<=1){
            int gn=pw[f<0][k<<1],g=1,x,y;
            for (int i=0;i<n;i+=k<<1,g=1)
                for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                    x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
        }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
    }
    inline PN operator - (const PN &A,const PN &B){
        static PN c;c.resize(max(A.size(),B.size()));
        for (int i=0;i<c.size();i++) AMOD(c[i]=i<A.size()?A[i]:0,i<B.size()?MOD-B[i]:0);return c;
    }
    inline PN operator * (const PN &A,const PN &B){
        static int n,a[maxt+5],m,b[maxt+5],c[maxt+5];static PN C;n=A.size();m=B.size();
        for (int i=0;i<n;i++) a[i]=A[i];for (int i=0;i<m;i++) b[i]=B[i];
        if (n<=250&&m<=250){
            for (int i=0;i<n+m-1;i++) c[i]=0;C.clear();
            for (int i=0;i<n;i++) for (int j=0;j<m;j++) AMOD(c[i+j],(LL)a[i]*b[j]%MOD);
            for (int i=0;i<n+m-1;i++) C.pb(c[i]);return C;
        }
        int t;for (t=1;t<n+m-1;t<<=1);Pre(t);
        for (int i=n;i<t;i++) a[i]=0;for (int i=m;i<t;i++) b[i]=0;
        NTT(a,t,1);NTT(b,t,1);for (int i=0;i<t;i++) c[i]=(LL)a[i]*b[i]%MOD;
        NTT(c,t,-1);C.clear();for (int i=0;i<n+m-1;i++) C.pb(c[i]);return C;
    }
    inline void Inv(int *a,int *b,int n){
        if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
        for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=b[i+n]=0;NTT(tem,n<<1,1);NTT(b,n<<1,1);
        for (int i=0;i<(n<<1);i++) tem[i]=(LL)b[i]*(2+MOD-(LL)b[i]*tem[i]%MOD)%MOD;
        NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
    }
    inline PN operator / (const PN &A,const PN &B){
        static int n,a[maxt+5],m,b[maxt+5],c[maxt+5];static PN C;n=A.size()-1;m=B.size()-1;
        if (n<m) return C.clear(),C.pb(0),C;int t;for (t=1;t<n-m+1;t<<=1);
        for (int i=0;i<(t<<1);i++) a[i]=b[i]=0;for (int i=0;i<n-m+1;i++) a[i]=A[n-i],b[i]=m-i<0?0:B[m-i];
        Inv(b,c,t);Pre(t<<1);NTT(a,t<<1,1);NTT(c,t<<1,1);for (int i=0;i<(t<<1);i++) c[i]=(LL)a[i]*c[i]%MOD;
        NTT(c,t<<1,-1);C.clear();for (int i=0;i<n-m+1;i++) C.pb(c[n-m-i]);return C;
    }
    inline PN operator % (const PN &A,const PN &B) {static PN C;C=A-A/B*B;C.resize(B.size()-1);return C;}
}
using namespace Poly;
void Build(int L,int R,int p=1){
    if (L==R) {P[p].pb((MOD-a[L])%MOD);P[p].pb(1);return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);P[p]=P[p<<1]*P[p<<1|1];
}
void Solve(int L,int R,int p=1){
    if (L==R) {ans[L]=F[0];return;}int mid=L+(R-L>>1);PN tem=F;
    F=tem%P[p<<1];Solve(L,mid,p<<1);F=tem%P[p<<1|1];Solve(mid+1,R,p<<1|1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=0,x;i<=n;i++) scanf("%d",&x),F.pb(x);
    for (int i=1;i<=m;i++) scanf("%d",&a[i]);Build(1,m);Solve(1,m);
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}