fork(5) download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27. const int Mod=998244353;
  28. const int alp=3;
  29.  
  30. int n,S;
  31. int C[MAX];
  32.  
  33. int dp[MAX];
  34.  
  35. namespace opt
  36. {
  37. 	int N;
  38. 	int a[MAX],b[MAX],w[MAX],tmp[MAX];
  39.  
  40. 	int Pow(int a,int b)
  41. 	{
  42. 		int k=1;
  43. 		for(;b;b/=2,a=(LL)a*a%Mod)
  44. 			if(b%2==1)
  45. 				k=(LL)k*a % Mod;
  46. 		return k;
  47. 	}
  48. 	void FFT(int *a,int S,int d)
  49. 	{
  50. 		if(d==N) return ;
  51. 		FFT(a,S,d<<1);
  52. 		FFT(a,S+d,d<<1);
  53. 		for(int i=S,j=S,p=0;i<N/2;i+=d,j+=d<<1,p+=d)
  54. 		{
  55. 			int G=a[j],K=a[j+d];
  56. 			tmp[i]=((LL)G+(LL)w[p]*K)%Mod;
  57. 			tmp[i+N/2]=((LL)G+(LL)w[p+N/2]*K)%Mod;
  58. 		}
  59. 		for(int i=S;i<N;i+=d)
  60. 			a[i]=tmp[i];
  61. 	}
  62. 	void conv(int *aa,int *bb,int *c,int n)
  63. 	{
  64. 		for(int i=0;i<n;++i)
  65. 			a[i]=aa[i],b[i]=bb[i];
  66.  
  67. 		if(n<=500)
  68. 		{
  69. 			for(int i=0;i<n*2;++i)
  70. 				c[i]=0;
  71. 			for(int i=0;i<n;++i)
  72. 				for(int j=0;j<n;++j)
  73. 					c[i+j]=( c[i+j]+(LL)a[i]*b[j] ) % Mod;
  74. 			for(int i=0;i<n;++i)
  75. 				a[i]=b[i]=0;
  76. 			return;
  77. 		}
  78. 		N=1;
  79. 		for(;N<n;N<<=1);
  80. 		N<<=1;
  81. 		w[0]=1;
  82.  
  83. 		w[1]=Pow(alp, (Mod - 1) / N);
  84. 		for(int i=2;i<=N;++i)
  85. 			w[i]=(LL)w[i-1]*w[1]%Mod;
  86. 		FFT(a,0,1);
  87. 		FFT(b,0,1);
  88. 		for(int i=0;i<N;++i)
  89. 			a[i]=(LL)a[i]*b[i]%Mod;
  90. 		for(int i=0;i<N;++i)
  91. 			b[i]=a[i?(N-i):0];
  92. 		FFT(b,0,1);
  93. 		int InvN=Pow(N,Mod-2);
  94. 		for(int i=0;i<N;++i)
  95. 		{
  96. 			c[i]=(LL)b[i]*InvN%Mod;
  97. 			a[i]=b[i]=0;
  98. 		}
  99. 	}
  100. }
  101.  
  102. int a[MAX],b[MAX],c[MAX];
  103.  
  104. void solve(int l,int r)
  105. {
  106. 	if(r==l+1)
  107. 		return;
  108. 	int mid=(l+r)/2;
  109. 	solve(l,mid);
  110.  
  111. 	int i;
  112. 	int need=r-l;//(r-1)-l+1
  113. 	REP2(i,0,need)
  114. 		a[i]=b[i]=0;
  115. 	if(need<=l)
  116. 	{
  117. 		REP2(i,0,mid-l)
  118. 			a[i]=dp[i+l];
  119. 		REP2(i,0,need)
  120. 			b[i]=dp[i];
  121. 		opt::conv(a,b,c,need);
  122. 		REP2(i,0,need)
  123. 		{
  124. 			c[i]*=2;
  125. 			if(c[i]>=Mod)
  126. 				c[i]-=Mod;
  127. 		}
  128. 	}
  129. 	else
  130. 	{
  131. 		REP2(i,0,mid-l)
  132. 			a[i]=b[i]=dp[i+l];
  133. 		opt::conv(a,b,c,need);
  134. 	}
  135. 	REP2(i,0,need)
  136. 	{
  137. 		a[i]=c[i];
  138. 		b[i]=C[i];
  139. 	}
  140. 	opt::conv(a,b,c,need);
  141. 	REP2(i,mid,r)
  142. 	{
  143. 		dp[i]+=c[i-l];
  144. 		if(dp[i]>=Mod)
  145. 			dp[i]-=Mod;
  146. 	}
  147. 	solve(mid,r);
  148. }
  149.  
  150. int main()
  151. {
  152. #ifndef ONLINE_JUDGE
  153. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  154. #endif
  155. 	int i;
  156. 	scanf("%d%d",&n,&S);
  157. 	REP(i,1,n)
  158. 	{
  159. 		int a;
  160. 		scanf("%d",&a);
  161. 		C[a]=1;
  162. 	}
  163. 	int N=1;
  164. 	for(;N<=S;N*=2)
  165. 		;
  166. 	dp[0]=1;
  167. 	solve(0,N);
  168.  
  169. 	REP(i,1,S)
  170. 		printf("%d\n",dp[i]);
  171. 	return 0;
  172. }
Success #stdin #stdout 0s 38456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TQ4lh8
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!