HDU-6061(NTT)

题意：给定\(f(x)\)求\(f(x-t)\)，系数对于\(998244353\)取模

其实本质依然是一个构造卷积

\[f(x)=\sum a_ix^i\]

\[f(x-t)=\sum a_i(x-t)^i\]

\((x-t)^i\)我们可以直接暴力用二项式定理展开，得到\(f(x-t)=\sum a_iC(i,j)t^{i-j}x^j\)

考虑每个\(i\)对于每个\(j\)的贡献，是一个组合数形式的，即\(\frac{i!}{j!(i-j)!}\)可以看到和差有关，所以可以卷积

对于初始的序列乘上\(i!\)，转移序列为\(\frac{t^{i-j}}{(i-j)!}\)，最终得到的序列再乘上一个\(\frac{1}{j!}\)即可

#include<bits/stdc++.h>
using namespace std;

//#define double long double

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } 
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); } 
//#define double long double

char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const double PI=acos(-1);

const int N=(1<<18)+4,P=998244353;
const int g=3;

bool be;
int n,m;
ll a[N],b[N];
int rev[N];

ll qpow(ll x,ll k){ 
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}

void NTT(int n,ll *a,int f){
    rep(i,0,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(reg int i=1;i<n;i<<=1) {
        ll w=qpow(f==1?3:(P+1)/3,(P-1)/i/2);
        for(reg int l=0;l<n;l+=i*2) {
            ll e=1;
            for(reg int j=l;j<l+i;j++,e=e*w%P) {
                ll t=a[j+i]*e%P;
                a[j+i]=(a[j]-t)%P;
                a[j]=(a[j]+t)%P;
            }
        }
    }
    if(f==-1) {
        ll base=qpow(n,P-2);
        rep(i,0,n-1) a[i]=a[i]*base%P;
    }
}

ll Inv[N],Fac[N],Pow[N];



bool ed;
int main(){
    Inv[0]=Inv[1]=Fac[0]=Fac[1]=1;
    rep(i,2,N-1) {
        Inv[i]=(P-P/i)*Inv[P%i]%P;
        Fac[i]=Fac[i-1]*i%P;
    }
    rep(i,1,N-1) Inv[i]=Inv[i-1]*Inv[i]%P;
    while(~scanf("%d",&n)) {
        rep(i,0,n) a[i]=rd()*Fac[i]%P;//初始序列
        int R=1,c=-1;
        while(R<=n*2) R<<=1,c++;
        rep(i,1,R) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
        ll x=0;
        rep(i,1,m=rd()) x=(x+rd())%P;//读入t
        x=-x;
        Pow[0]=1;
        rep(i,1,R) Pow[i]=Pow[i-1]*x%P;
        rep(i,0,n) b[n-i]=Pow[i]*Inv[i]%P;//转移序列
        NTT(R,a,1),NTT(R,b,1);
        rep(i,0,R) a[i]=a[i]*b[i]%P;
        NTT(R,a,-1);
        rep(i,0,n) printf("%lld ",(a[i+n]*Inv[i]%P+P)%P); puts(""); //最终处理
        rep(i,0,R) a[i]=b[i]=0;
    }
}