粘板子:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int MOD = 998244353; const int N = 100050; const int M = N*3; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } template<typename T>inline void Mod(T&x){if(x>=MOD)x-=MOD;} int fastpow(int x,int y) { int ret = 1; while(y) { if(y&1)ret=1ll*ret*x%MOD; x=1ll*x*x%MOD;y>>=1; } return ret; } int inv(int x){return fastpow(x,MOD-2);} int to[M],lim,L,LL[M]; void init(int len) { lim=LL[2]=1; while(lim<len)lim<<=1,LL[lim<<1]=LL[lim]+1; } void get_lim(int len) { lim = len,L = LL[len]; for(int i=1;i<=lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(L-1))); } void ntt(int*a,int len,int k) { for(int i=0;i<len;i++) if(i<to[i])swap(a[i],a[to[i]]); for(int i=1;i<len;i<<=1) { int w0 = fastpow(3,(MOD-1)/(i<<1)); for(int j=0;j<len;j+=(i<<1)) { int w = 1; for(int o=0;o<i;o++,w=1ll*w*w0%MOD) { int w1 = a[j+o],w2 = 1ll*a[j+o+i]*w%MOD; Mod(a[j+o] = w1+w2); Mod(a[j+o+i] = w1+MOD-w2); } } } if(k==-1) { for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]); int Inv = inv(len); for(int i=0;i<len;i++)a[i]=1ll*a[i]*Inv%MOD; } } int a[M],b[M],c[M]; int f[M],g[M],n; void cdq(int l,int r) { if(l==r)return ; int mid = (l+r)>>1; cdq(l,mid); get_lim(2*(r-l+1)); for(int i=0;i<lim;i++)a[i]=b[i]=0; for(int i=0;i<=mid-l;i++)a[i]=f[l+i]; for(int i=1;i<=r-l+1;i++)b[i]=g[i]; ntt(a,lim,1),ntt(b,lim,1); for(int i=0;i<=lim;i++)c[i]=1ll*a[i]*b[i]%MOD; ntt(c,lim,-1); for(int i=mid+1-l;i<=r-l;i++)Mod(f[i+l]+=c[i]); cdq(mid+1,r); } int main() { // freopen("tt.in","r",stdin); read(n);init(n<<1);f[0]=1; for(int i=1;i<n;i++)read(g[i]); cdq(0,lim-1); for(int i=0;i<n;i++)printf("%d ",f[i]); puts(""); return 0; }View Code