这是CDQ入门题，不要被题目名骗了，这核心根本不在不在FFT上啊=。=
因为后面的项的计算依赖于前面的项，不能直接FFT。所以用CDQ的思想，算出前面然后考虑给后面的贡献
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005,mod=998244353; 6 int a[4*N],b[4*N],rev[4*N],f[N],g[N],n,G,Gi; 7 void exGCD(int a,int b,int &x,int &y) 8 { 9 if(!b) {x=1,y=0; return ;} 10 exGCD(b,a%b,y,x),y-=a/b*x; 11 } 12 int Qpow(int x,int k) 13 { 14 if(k==1) return x; 15 int tmp=Qpow(x,k/2); 16 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 17 } 18 int Inv(int x,int m) 19 { 20 int xx,yy; 21 exGCD(x,m,xx,yy); 22 return (xx%m+m)%m; 23 } 24 void NTT(int *arr,int len,int typ) 25 { 26 for(int i=0;i<=len;i++) 27 if(rev[i]>i) swap(arr[rev[i]],arr[i]); 28 for(int i=2;i<=len;i<<=1) 29 { 30 int lth=i>>1,ort=Qpow(~typ?G:Gi,(mod-1)/i); 31 for(int j=0;j<len;j+=i) 32 { 33 int ori=1,tmp; 34 for(int k=j;k<j+lth;k++,ori=1ll*ori*ort%mod) 35 { 36 tmp=1ll*ori*arr[k+lth]%mod; 37 arr[k+lth]=(arr[k]-tmp+mod)%mod; 38 arr[k]=(arr[k]+tmp)%mod; 39 } 40 } 41 } 42 if(typ==-1) 43 for(int i=0,ni=Inv(len,mod);i<len;i++) 44 arr[i]=1ll*arr[i]*ni%mod; 45 } 46 void CDQ(int l,int r,int mid) 47 { 48 int len=r-l+1,m=1; 49 for(int i=l;i<=mid;i++) a[i-l]=f[i]; 50 for(int i=0;i<len;i++) b[i]=g[i]; len+=mid-l+1; 51 while(m<=len) m<<=1; 52 for(int i=1;i<=m;i++) rev[i]=(rev[i>>1]>>1)+(i&1)*(m>>1); 53 NTT(a,m,1),NTT(b,m,1); 54 for(int i=0;i<=m;i++) a[i]=1ll*a[i]*b[i]%mod; 55 NTT(a,m,-1); 56 for(int i=mid+1;i<=r;i++) f[i]+=a[i-l],f[i]%=mod; 57 for(int i=0;i<=m;i++) a[i]=b[i]=0; 58 } 59 void Divide(int l,int r) 60 { 61 if(l==r) return; 62 int mid=(l+r)/2; 63 Divide(l,mid),CDQ(l,r,mid),Divide(mid+1,r); 64 } 65 int main() 66 { 67 scanf("%d",&n); 68 for(int i=1;i<n;i++) scanf("%d",&g[i]); 69 f[0]=1,G=3,Gi=Inv(G,mod),Divide(0,n-1); 70 for(int i=0;i<n;i++) printf("%d ",f[i]); 71 return 0; 72 }