$LuoguP4721$
——————————————–
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define mo 998244353 #define ll long long #define G 3 using namespace std; const int N=300010; int n,g[N],f[N],A[N],B[N],C[N],w[N],L; ll INV; ll mi(ll x,int y) { ll ans=1; while (y) { if (y&1) ans=ans*x%mo; x=x*x%mo; y>>=1; } return ans; } void NTT(int *a,int f) { for (int i=0,j=0;i<L;i++) { if (i>j) swap(a[i],a[j]); for (int k=L>>1;(j^=k)<k;k>>=1); } for (int len=2;len<=L;len<<=1) { int l=len>>1; ll W=mi(G,(mo-1)/len); for (int i=1;i<l;i++) w[i]=W*w[i-1]%mo; for (int i=0;i<L;i+=len) for (int j=0;j<l;j++) { int x=a[i+j],y=(ll)w[j]*a[i+j+l]%mo; a[i+j]=(x+y>=mo)?x+y-mo:x+y;a[i+j+l]=(x-y<0)?x-y+mo:x-y; } } if (f==-1) { for (int i=1;i<L/2;i++) swap(a[i],a[L-i]); for (int i=0;i<L;i++) a[i]=(ll)a[i]*INV%mo; } } void pre(int len) { L=1; while (L<len) L<<=1; INV=mi(L,mo-2); for (int i=0;i<L;i++) A[i]=B[i]=C[i]=0; w[0]=1; } void mul(int *A,int *B,int *C,int a,int b) { NTT(A,1);NTT(B,1); for (int i=0;i<L;i++) C[i]=(ll)A[i]*B[i]%mo; NTT(C,-1); } void solve(int l,int r) { if (l==r) return; int mid=(l+r)>>1; solve(l,mid); pre(r-l+1+mid-l+1); for (int i=0;i<mid-l+1;i++) A[i]=f[l+i]; for (int i=1;i<=r-l;i++) B[i]=g[i]; mul(A,B,C,mid-l+1,r-l+1); for (int i=mid-l+1;i<=r-l;i++) f[i+l]=(f[i+l]+C[i])%mo; solve(mid+1,r); } int main() { scanf("%d",&n); for (int i=1;i<n;i++) scanf("%d",&g[i]); f[0]=1; solve(0,n-1); for (int i=0;i<n;i++) printf("%d%c",f[i]," \n"[i==n-1]); return 0; } |
