fork(3) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef long long s64;
  8.  
  9. const int Mod = 998244353;
  10. const int Mod_G = 3;
  11.  
  12. const int MaxCN = 100000;
  13. const int MaxS = 100000;
  14.  
  15. struct modint
  16. {
  17. 	int a;
  18.  
  19. 	modint(){}
  20. 	modint(int _a)
  21. 	{
  22. 		a = _a % Mod;
  23. 		if (a < 0)
  24. 			a += Mod;
  25. 	}
  26. 	modint(s64 _a)
  27. 	{
  28. 		a = _a % Mod;
  29. 		if (a < 0)
  30. 			a += Mod;
  31. 	}
  32.  
  33. 	inline modint operator-() const
  34. 	{
  35. 		return -a;
  36. 	}
  37. 	inline modint inv() const
  38. 	{
  39. 		int x1 = 1, x2 = 0, x3 = Mod;
  40. 		int y1 = 0, y2 = 1, y3 = a;
  41. 		while (y3 != 1)
  42. 		{
  43. 			int k = x3 / y3;
  44. 			x1 -= y1 * k, x2 -= y2 * k, x3 -= y3 * k;
  45. 			swap(x1, y1), swap(x2, y2), swap(x3, y3);
  46. 		}
  47. 		return y2 >= 0 ? y2 : y2 + Mod;
  48. 	}
  49.  
  50. 	friend inline modint operator+(const modint &lhs, const modint &rhs)
  51. 	{
  52. 		return lhs.a + rhs.a;
  53. 	}
  54. 	friend inline modint operator-(const modint &lhs, const modint &rhs)
  55. 	{
  56. 		return lhs.a - rhs.a;
  57. 	}
  58. 	friend inline modint operator*(const modint &lhs, const modint &rhs)
  59. 	{
  60. 		return (s64)lhs.a * rhs.a;
  61. 	}
  62. 	friend inline modint operator/(const modint &lhs, const modint &rhs)
  63. 	{
  64. 		return lhs * rhs.inv();
  65. 	}
  66.  
  67. 	inline modint div2() const
  68. 	{
  69. 		return (s64)a * ((Mod + 1) / 2);
  70. 	}
  71. };
  72.  
  73. inline modint modpow(const modint &a, const int &n)
  74. {
  75. 	modint res = 1;
  76. 	modint t = a;
  77. 	for (int i = n; i > 0; i >>= 1)
  78. 	{
  79. 		if (i & 1)
  80. 			res = res * t;
  81. 		t = t * t;
  82. 	}
  83. 	return res;
  84. }
  85.  
  86. const int MaxN = 131072;
  87. const int MaxTN = MaxN * 2;
  88.  
  89. modint prePowG[MaxTN];
  90.  
  91. void fft(int n, modint *a, int step, modint *out)
  92. {
  93. 	if (n == 1)
  94. 	{
  95. 		out[0] = a[0];
  96. 		return;
  97. 	}
  98. 	int m = n / 2;
  99. 	fft(m, a, step + 1, out);
  100. 	fft(m, a + (1 << step), step + 1, out + m);
  101. 	for (int i = 0; i < m; i++)
  102. 	{
  103. 		modint e = out[i], o = out[i + m] * prePowG[i << step];
  104. 		out[i] = e + o;
  105. 		out[i + m] = e - o;
  106. 	}
  107. }
  108.  
  109. void poly_mulTo(int n, modint *f, modint *g)
  110. {
  111. 	/*static modint c[MaxN];
  112. 	for (int i = 0; i < n; i++)
  113. 		c[i] = 0;
  114. 	for (int i = 0; i < n; i++)
  115. 		for (int j = 0; i + j < n; j++)
  116. 			c[i + j] = c[i + j] + f[i] * g[j];
  117. 	copy(c, c + n, f);
  118. 	return;*/
  119.  
  120. 	int tn = n * 2;
  121. 	static modint tf[MaxTN], tg[MaxTN];
  122. 	copy(f, f + n, tf), fill(tf + n, tf + tn, modint(0));
  123. 	copy(g, g + n, tg), fill(tg + n, tg + tn, modint(0));
  124.  
  125. 	modint rg = modpow(Mod_G, (Mod - 1) / tn);
  126. 	prePowG[0] = 1;
  127. 	for (int i = 1; i < tn; i++)
  128. 		prePowG[i] = prePowG[i - 1] * rg;
  129.  
  130. 	static modint dftF[MaxTN], dftG[MaxTN];
  131. 	fft(tn, tf, 0, dftF);
  132. 	fft(tn, tg, 0, dftG);
  133.  
  134. 	for (int i = 0; i < tn; i++)
  135. 		dftF[i] = dftF[i] * dftG[i];
  136.  
  137. 	reverse(prePowG + 1, prePowG + tn);
  138. 	fft(tn, dftF, 0, tf);
  139. 	reverse(prePowG + 1, prePowG + tn);
  140.  
  141. 	modint revTN = modint(tn).inv();
  142. 	for (int i = 0; i < n; i++)
  143. 		f[i] = tf[i] * revTN;
  144. }
  145.  
  146. void poly_inv(int n, modint *f, modint *r)
  147. {
  148. 	// assert(f[0] == 1)
  149. 	fill(r, r + n, modint(0));
  150. 	r[0] = 1;
  151. 	for (int m = 2; m <= n; m <<= 1)
  152. 	{
  153. 		int h = m / 2;
  154. 		static modint nr[MaxN];
  155. 		copy(f, f + m, nr);
  156. 		poly_mulTo(m, nr, r);
  157. 		fill(nr, nr + h, modint(0));
  158. 		for (int i = h; i < m; i++)
  159. 			nr[i] = -nr[i];
  160. 		poly_mulTo(m, nr, r);
  161. 		copy(nr + h, nr + m, r + h);
  162. 	}
  163. }
  164.  
  165. void poly_sqrt(int n, modint *f, modint *s)
  166. {
  167. 	// assert(f[0] == 1)
  168. 	fill(s, s + n, modint(0));
  169. 	s[0] = 1;
  170.  
  171. 	static modint rs[MaxN];
  172. 	fill(rs, rs + n, modint(0));
  173. 	rs[0] = 1;
  174. 	for (int m = 2; m <= n; m <<= 1)
  175. 	{
  176. 		int h = m / 2;
  177. 		static modint nrs[MaxN];
  178. 		copy(s, s + h, nrs), fill(nrs + h, nrs + m, modint(0));
  179. 		poly_mulTo(m, nrs, rs);
  180. 		fill(nrs, nrs + h, modint(0));
  181. 		for (int i = h; i < m; i++)
  182. 			nrs[i] = -nrs[i];
  183. 		poly_mulTo(m, nrs, rs);
  184. 		copy(rs, rs + h, nrs);
  185. 		poly_mulTo(m, nrs, f);
  186. 		for (int i = h; i < m; i++)
  187. 			s[i] = nrs[i].div2();
  188. 		copy(s, s + m, nrs);
  189. 		poly_mulTo(m, nrs, rs);
  190. 		fill(nrs, nrs + h, modint(0));
  191. 		for (int i = h; i < m; i++)
  192. 			nrs[i] = -nrs[i];
  193. 		poly_mulTo(m, nrs, rs);
  194. 		copy(nrs + h, nrs + m, rs + h);
  195. 	}
  196. }
  197.  
  198. int main()
  199. {
  200. 	int c_n, s;
  201. 	static int c[MaxCN];
  202.  
  203. 	cin >> c_n >> s;
  204. 	for (int i = 0; i < c_n; i++)
  205. 		scanf("%d", &c[i]);
  206.  
  207. 	int n = 1;
  208. 	while (n < s + 1)
  209. 		n <<= 1;
  210.  
  211. 	static modint fD[MaxN];
  212. 	fD[0] = 1;
  213. 	for (int i = 0; i < c_n; i++)
  214. 		if (c[i] <= s)
  215. 			fD[c[i]] = -4;
  216.  
  217. 	static modint fB[MaxN];
  218. 	poly_sqrt(n, fD, fB);
  219.  
  220. 	fB[0] = fB[0] + 1;
  221.  
  222. 	for (int i = 0; i < n; i++)
  223. 		fB[i] = fB[i].div2();
  224.  
  225. 	static modint f[MaxN];
  226. 	poly_inv(n, fB, f);
  227.  
  228. 	for (int i = 1; i <= s; i++)
  229. 		printf("%d\n", f[i].a);
  230.  
  231. 	return 0;
  232. }
Success #stdin #stdout 0s 11928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uQYLfQ
language:
C++ (gcc 8.3)
created:
9 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!