Submit Info #33464

Problem Lang User Status Time Memory
Polynomial Taylor Shift pypy3 Eki1009 AC 786 ms 165.29 MiB

ケース詳細
Name Status Time Memory
example_00 AC 89 ms 33.32 MiB
example_01 AC 95 ms 33.11 MiB
fft_killer_00 AC 786 ms 157.24 MiB
fft_killer_01 AC 773 ms 157.34 MiB
max_random_00 AC 776 ms 160.95 MiB
max_random_01 AC 771 ms 160.95 MiB
medium_00 AC 133 ms 34.91 MiB
medium_01 AC 139 ms 35.01 MiB
medium_02 AC 138 ms 35.34 MiB
medium_all_zero_00 AC 132 ms 35.03 MiB
medium_c_zero_00 AC 133 ms 34.95 MiB
random_00 AC 727 ms 139.92 MiB
random_01 AC 746 ms 165.29 MiB
random_02 AC 197 ms 48.32 MiB
small_00 AC 91 ms 33.33 MiB
small_01 AC 92 ms 33.27 MiB
small_02 AC 89 ms 33.34 MiB
small_03 AC 90 ms 33.24 MiB
small_04 AC 94 ms 33.29 MiB
small_05 AC 92 ms 33.33 MiB
small_06 AC 89 ms 33.33 MiB
small_07 AC 95 ms 33.28 MiB
small_08 AC 92 ms 33.28 MiB
small_09 AC 96 ms 33.26 MiB
small_10 AC 92 ms 33.26 MiB
small_11 AC 89 ms 33.34 MiB
small_12 AC 87 ms 33.24 MiB
small_13 AC 93 ms 33.24 MiB
small_14 AC 90 ms 33.34 MiB
small_15 AC 95 ms 33.29 MiB

mod = 998244353 sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497) sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951) import random def sqrt_mod(a): a %= mod if a == 0: return 0 k = (mod - 1) // 2 if pow(a, k, mod) != 1: return -1 while 1: c = random.randint(2, mod - 1) theta = (c * c - a) % mod if theta == 0: return c if pow(theta, k, mod) == mod - 1: break k += 1 f0, f1 = c, 1 g0, g1 = 1, 0 while k: if k & 1: g0, g1 = f0 * g0 + theta * f1 * g1, f1 * g0 + f0 * g1 f0, f1 = f0 * f0 + theta * f1 * f1, 2 * f0 * f1 f0 %= mod f1 %= mod g0 %= mod g1 %= mod k >>= 1 return g0 def inv_mod(a): a %= mod if a == 0: return 0 s, t = mod, a m0, m1 = 0, 1 while t: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += mod // s return m0 fac_ = [1, 1] finv_ = [1, 1] inv_ = [1, 1] def fac(i): while i >= len(fac_): fac_.append(fac_[-1] * len(fac_) % mod) return fac_[i] def finv(i): while i >= len(inv_): inv_.append((-inv_[mod % len(inv_)]) * (mod // len(inv_)) % mod) while i >= len(finv_): finv_.append(finv_[-1] * inv_[len(finv_)] % mod) return finv_[i] def inv(i): while i >= len(inv_): inv_.append((-inv_[mod % len(inv_)]) * (mod // len(inv_)) % mod) return inv_[i] def butterfly(A): n = len(A) h = (n - 1).bit_length() for ph in range(1, h + 1): w = 1 << (ph - 1) p = 1 << (h - ph) now = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = A[i + offset] r = A[i + offset + p] * now A[i + offset] = (l + r) % mod A[i + offset + p] = (l - r) % mod now *= sum_e[(~s & -~s).bit_length() - 1] now %= mod def butterfly_inv(A): n = len(A) h = (n - 1).bit_length() for ph in range(h, 0, -1): w = 1 << (ph - 1) p = 1 << (h - ph) inow = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = A[i + offset] r = A[i + offset + p] A[i + offset] = (l + r) % mod A[i + offset + p] = (mod + l - r) * inow % mod inow *= sum_ie[(~s & -~s).bit_length() - 1] inow %= mod def convolution(_A, _B): A = _A.copy() B = _B.copy() n = len(A) m = len(B) if not n or not m: return [] if min(n, m) <= 60: if n < m: n, m = m, n A, B = B, A res = [0] * (n + m - 1) for i in range(n): for j in range(m): res[i + j] += A[i] * B[j] res[i + j] %= mod return res z = 1 << (n + m - 2).bit_length() A += [0] * (z - n) B += [0] * (z - m) butterfly(A) butterfly(B) for i in range(z): A[i] *= B[i] A[i] %= mod butterfly_inv(A) A = A[:n + m - 1] iz = inv_mod(z) for i in range(n + m - 1): A[i] *= iz A[i] %= mod return A def autocorrelation(_A): A = _A.copy() n = len(A) if not n: return [] if n <= 60: res = [0] * (n + n - 1) for i in range(n): for j in range(n): res[i + j] += A[i] * A[j] res[i + j] %= mod return res z = 1 << (n + n - 2).bit_length() A += [0] * (z - n) butterfly(A) for i in range(z): A[i] *= A[i] A[i] %= mod butterfly_inv(A) A = A[:n + n - 1] iz = inv_mod(z) for i in range(n + n - 1): A[i] *= iz A[i] %= mod return A class FormalPowerSeries: def __init__(self, poly=[]): self.poly = [p % mod for p in poly] def __getitem__(self, key): if isinstance(key, slice): res = self.poly[key] return FormalPowerSeries(res) else: if key < 0: raise IndexError("list index out of range") if key >= len(self.poly): return 0 else: return self.poly[key] def __setitem__(self, key, value): if key < 0: raise IndexError("list index out of range") if key >= len(self.poly): self.poly += [0] * (key - len(self.poly) + 1) self.poly[key] = value % mod def __len__(self): return len(self.poly) def resize(self, size): if len(self) >= size: return self[:size] else: return FormalPowerSeries(self.poly + [0] * (size - len(self))) def times(self, n): n %= mod res = [p * n for p in self.poly] return FormalPowerSeries(res) def __pos__(self): return self def __neg__(self): return self.times(-1) def __add__(self, other): if other.__class__ == FormalPowerSeries: s = len(self) t = len(other) n = min(s, t) res = [self[i] + other[i] for i in range(n)] if s >= t: res += self.poly[t:] else: res += other.poly[s:] return FormalPowerSeries(res) else: return self + FormalPowerSeries([other]) def __radd__(self, other): return self + other def __sub__(self, other): return self + (-other) def __rsub__(self, other): return (-self) + other def __mul__(self, other): if other.__class__ == FormalPowerSeries: res = convolution(self.poly, other.poly) return FormalPowerSeries(res) else: return self.times(other) def __rmul__(self, other): return self.times(other) def __lshift__(self, other): return FormalPowerSeries(([0] * other) + self.poly) def __rshift__(self, other): return self[other:] def square(self): res = autocorrelation(self.poly) return FormalPowerSeries(res) def inv(self, deg=-1): assert self[0] if deg == -1: deg = len(self) - 1 r = inv_mod(self[0]) m = 1 T = [0] * (deg + 1) T[0] = r res = FormalPowerSeries(T) t = 748683265 iz = 1 while m <= deg: F = [0] * (2 * m) G = [0] * (2 * m) for j in range(min(len(self), 2 * m)): F[j] = self[j] for j in range(m): G[j] = res[j] butterfly(F) butterfly(G) for j in range(2 * m): F[j] *= G[j] F[j] %= mod butterfly_inv(F) for j in range(m): F[j] = 0 butterfly(F) for j in range(2 * m): F[j] *= G[j] F[j] %= mod butterfly_inv(F) iz *= t iz %= mod for j in range(m, min(2 * m, deg + 1)): res[j] = -F[j]*iz m <<= 1 return res #P/Q def __truediv__(self, other): if other.__class__ == FormalPowerSeries: return (self * other.inv()) else: return self * inv_mod(other) def __rtruediv__(self, other): return other * self.inv() #P,Qを多項式として見たときのPをQで割った商を求める def __floordiv__(self, other): if other.__class__ == FormalPowerSeries: if len(self) < len(other): return FormalPowerSeries() else: m = len(self) - len(other) + 1 res = (self[-1:-m-1:-1] * other[::-1].inv(m))[m-1::-1] return res else: return self * inv_mod(other) def __rfloordiv__(self, other): return other * self.inv() def __mod__(self, other): if len(self) < len(other): return self[:] else: res = self[:len(other) - 1] - ((self // other) * other)[:len(other) - 1] return res def differentiate(self): res = [k * p for k, p in enumerate(self.poly[1:], 1)] return FormalPowerSeries(res) def integrate(self): res = [0] + [inv(k) * p for k, p in enumerate(self.poly, 1)] return FormalPowerSeries(res) def log(self, deg=-1): if deg == -1: deg = len(self) - 1 return (self.differentiate() / self)[:deg].integrate() def exp(self, deg=-1): if deg == -1: deg = len(self) - 1 res = FormalPowerSeries([1]) G = FormalPowerSeries([1]) df = self.differentiate() m = 1 while m <= deg: G = G * 2 - (res * G.square())[:m] m <<= 1 dft = df[:m] W = dft + (G * (res.differentiate() - (res * dft)[:m]))[:m] res += (res * (self[:m] - W.integrate()[:m]))[:m] return res[:deg + 1] def __pow__(self, n, deg=-1): if deg == -1: deg = len(self) - 1 m = abs(n) for d, p in enumerate(self.poly): if p: break else: return FormalPowerSeries() if d * m >= len(self): return FormalPowerSeries() G = self[d:] G = ((G * inv_mod(p)).log() * m).exp() * pow(p, m, mod) res = FormalPowerSeries([0] * (d * m) + G.poly) if n >= 0: return res[:deg + 1] else: return res.inv()[:deg + 1] def sqrt(self, deg=-1): if deg == -1: deg = len(self) - 1 if len(self) == 0: return FormalPowerSeries() if self[0] == 0: for d in range(1, len(self)): if self[d]: if d & 1: return -1 if deg < d // 2: break res = self[d:].sqrt(deg - d // 2) if res == -1: return -1 res = res << (d // 2) return res return FormalPowerSeries() sqr = sqrt_mod(self[0]) if sqr == -1: return -1 T = [0] * (deg + 1) T[0] = sqr res = FormalPowerSeries(T) two_inv = (mod + 1) // 2 m = 1 while m <= deg: m <<= 1 k = min(m, deg + 1) res += (self[:m] * res.inv(m - 1))[:k] res *= two_inv return res #各p_i(0<=i<m)についてf(p_i)を求める def multipoint_evaluation(self, P): m = len(P) size = 1 << (m - 1).bit_length() G = [FormalPowerSeries([1]) for _ in range(2 * size)] for i in range(m): G[size + i] = FormalPowerSeries([-P[i], 1]) for i in range(size - 1, 0, -1): G[i] = G[2 * i] * G[2 * i + 1] G[1] = self % G[1] for i in range(2, size + m): G[i] = G[i >> 1] % G[i] res = [G[i][0] for i in range(size, size + m)] return res def taylor_shift(self, a): a %= mod n = len(self) t = 1 F = self[:] G = FormalPowerSeries([0] * n) for i in range(n): F[i] *= fac(i) for i in range(n): G[i] = t * finv(i) t = t * a % mod res = (F * G[::-1])[n - 1:] for i in range(n): res[i] *= finv(i) return res #[x^n]P/Qを求める def poly_coef(Q, P, n): while n: R = [0] * len(Q.poly) for i, q in enumerate(Q.poly): if i & 1: R[i] = -q else: R[i] = q R = FormalPowerSeries(R) P = P * R Q = Q * R if n & 1: P = P[1::2] else: P = P[::2] Q = Q[::2] n >>= 1 return P[0] def subset_sum(A, limit): C = [0] * (limit + 1) for a in A: C[a] += 1 res = FormalPowerSeries([0] * (limit + 1)) for i in range(1, limit + 1): for k in range(1, limit // i + 1): j = i * k res[j] += ((k & 1) * 2 - 1) * C[i] * inv(k) return res.exp(limit).poly def partition_function(n): res = FormalPowerSeries([0] * (n + 1)) res[0] = 1 for k in range(1, n+1): k1 = k * (3 * k + 1 )// 2 k2 = k * (3 * k - 1) // 2 if k2 > n: break if k1 <= n: res[k1] += 1 - (k & 1) * 2 if k2 <= n: res[k2] += 1 - (k & 1) * 2 return res.inv().poly def bernoulli_number(n): n += 1 Q = FormalPowerSeries([finv(i + 1) for i in range(n)]).inv(n - 1) res = [v * fac(i) % mod for i, v in enumerate(Q.poly)] return res def stirling_first(n): P = [] a = n while a: if a & 1: P.append(1) P.append(0) a >>= 1 res = FormalPowerSeries([1]) t = 0 for x in P[::-1]: if x: res *= FormalPowerSeries([-t, 1]) t += 1 else: res *= res.taylor_shift(-t) t *= 2 return res.poly def stirling_second(n): F = FormalPowerSeries([0] * (n + 1)) G = FormalPowerSeries([0] * (n + 1)) for i in range(n + 1): F[i] = pow(i, n, mod) * finv(i) G[i] = (1 - (i & 1) * 2) * finv(i) return (F * G)[:n + 1].poly def polynominal_interpolation(X, Y): n = len(X) size = 1 << (n - 1).bit_length() mul_li = [FormalPowerSeries([1]) for _ in range(2 * size)] g_li = [0] * (2 * size) for i in range(n): mul_li[size + i] = FormalPowerSeries([-X[i], 1]) for i in range(size - 1, 0, -1): mul_li[i] = mul_li[2 * i] * mul_li[2 * i + 1] g_li[1] = mul_li[1].differentiate() % mul_li[1] for i in range(2, size + n): g_li[i] = g_li[i >> 1] % mul_li[i] for i in range(n): g_li[size + i] = FormalPowerSeries([Y[i] * inv_mod(g_li[size + i][0])]) for i in range(size - 1, 0, -1): g_li[i] = g_li[2 * i] * mul_li[2 * i + 1] + g_li[2 * i + 1] * mul_li[2 * i] return g_li[1][:n] import sys input = sys.stdin.readline n, c = map(int, input().split()) A = tuple(map(int, input().split())) P = FormalPowerSeries(A) ans = P.taylor_shift(c).poly print(*ans)