import numpy as np from numpy.fft import rfft,irfft mod = 998244353 def convolve(f, g): fft_len = 1 while 2 * fft_len < len(f) + len(g) - 1: fft_len *= 2 fft_len *= 2 Ff = np.fft.rfft(f, fft_len) Fg = np.fft.rfft(g, fft_len) Fh = Ff * Fg h = np.fft.irfft(Fh, fft_len) h = np.rint(h).astype(np.int64) return h[:len(f) + len(g) - 1] def convolve2(f, g): f1, f2 = np.divmod(f, 1 << 15) g1, g2 = np.divmod(g, 1 << 15) a = convolve(f1, g1)%mod c = convolve(f2, g2)%mod b = (convolve(f1+f2, g1+g2)-(a+c))%mod h = (a << 30) + (b << 15) + c return h%mod class poly(object): def __init__(self, coef): if isinstance(coef, int): coef = [coef] self.coef = np.array([c%mod for c in coef], dtype=np.int64) self.n = len(coef) def __getitem__(self, item): return poly(self.coef[item]) def __setitem__(self, key, value): self.coef[key] = value%mod def __len__(self): return self.n def __add__(p, q): n = max(len(p),len(q)) return poly((p.pad(n).coef+q.pad(n).coef)%mod) def __sub__(p, q): n = max(len(p),len(q)) p.pad(n) q.pad(n) return poly((p.pad(n).coef-q.pad(n).coef)%mod) def __mul__(p, q): return poly(convolve2(p.coef,q.coef)) def __truediv__(p, q): return p*q.inv() def pad(self, n): if len(self) 0: s *= self.tree[i] i -= i & -i return s def prod(self, i, x): i += 1 while i <= self.size: self.tree[i] *= x i += i & -i bit = BIT(N) for i in tqdm(range(N)): bit.prod(i, poly([1,-A[i]])) poly_ans = poly(-1)*bit.prod_tot(N-1).log(M+1) ans = [] for i in range(M): ans.append((i+1)*poly_ans.coef[i+1]%mod) print(*ans)