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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include <bits/stdc++.h> #define MAXN 500005 #define MOD 998244353 #define invG 332748118 #define GG 3 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inline int ksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } int r[MAXN],C[MAXN]; inline void NTT(int *A,int n,int type){ for (register int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (register int i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?GG:invG,(MOD-1)/R); for (register int j=0;j<n;j+=R){ int g=1; for (register int k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } } inline int get_inv(int x){ return ksm(x,MOD-2); } int m,L; inline void Init(int len){ m=1,L=0; while (m<2*len) m<<=1,L++; for (register int i=0;i<m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } } inline void Inv(int *A,int *B,int len){ if (len==1){ B[0]=get_inv(A[0]); return ; } Inv(A,B,(len+1)>>1); Init(len); for (register int i=0;i<len;++i) C[i]=A[i]; for (register int i=len;i<m;++i) C[i]=0; NTT(C,m,1),NTT(B,m,1); for (register int i=0;i<m;++i){ B[i]=(2ll-1ll*B[i]*C[i]%MOD+MOD)*B[i]%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (register int i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD; for (register int i=len;i<m;++i) B[i]=0; } int D[MAXN],inv2; inline void Sqrt(int *A,int *B,int len){ if (len==1){ B[0]=A[0]; return ; } Sqrt(A,B,(len+1)>>1); for (register int i=0;i<(len<<1);++i) D[i]=0; Inv(B,D,len); Init(len); for (register int i=0;i<len;++i) C[i]=A[i]; for (register int i=len;i<m;++i) C[i]=0; NTT(B,m,1),NTT(C,m,1),NTT(D,m,1); for (register int i=0;i<m;++i){ B[i]=1ll*inv2*(1ll*C[i]*D[i]%MOD+B[i])%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (register int i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD; for (register int i=len;i<m;++i) B[i]=0; } int G[MAXN],F[MAXN]; int S1[MAXN],Ans1[MAXN]; int S2[MAXN],Ans2[MAXN]; int main(){ int n=read(),len=read(); inv2=ksm(2,MOD-2); G[0]=1; for (register int i=1;i<=n;++i){ G[read()]++; } S1[0]=1; for (register int i=1;i<=len;++i){ S1[i]=(-4ll*G[i]%MOD+MOD)%MOD; } Sqrt(S1,Ans1,len+1); Ans1[0]=(Ans1[0]+1)%MOD; Inv(Ans1,Ans2,len+1); for (register int i=1;i<=len;++i){ printf("%d\n",2ll*Ans2[i]%MOD); } }
|