Submit Info #28707

Problem Lang User Status Time Memory
Polynomial Taylor Shift pypy3 Kiri8128 AC 606 ms 170.73 MiB

ケース詳細
Name Status Time Memory
example_00 AC 50 ms 29.88 MiB
example_01 AC 52 ms 29.82 MiB
fft_killer_00 AC 596 ms 164.63 MiB
fft_killer_01 AC 598 ms 164.69 MiB
max_random_00 AC 606 ms 170.73 MiB
max_random_01 AC 599 ms 164.61 MiB
medium_00 AC 77 ms 30.96 MiB
medium_01 AC 82 ms 31.47 MiB
medium_02 AC 74 ms 31.47 MiB
medium_all_zero_00 AC 77 ms 30.98 MiB
medium_c_zero_00 AC 81 ms 31.04 MiB
random_00 AC 574 ms 148.42 MiB
random_01 AC 586 ms 159.16 MiB
random_02 AC 138 ms 46.00 MiB
small_00 AC 54 ms 29.84 MiB
small_01 AC 56 ms 29.87 MiB
small_02 AC 55 ms 29.80 MiB
small_03 AC 55 ms 29.80 MiB
small_04 AC 53 ms 29.81 MiB
small_05 AC 49 ms 29.90 MiB
small_06 AC 56 ms 29.88 MiB
small_07 AC 53 ms 29.83 MiB
small_08 AC 55 ms 29.89 MiB
small_09 AC 53 ms 29.89 MiB
small_10 AC 53 ms 29.88 MiB
small_11 AC 54 ms 29.77 MiB
small_12 AC 54 ms 29.87 MiB
small_13 AC 50 ms 29.71 MiB
small_14 AC 56 ms 29.87 MiB
small_15 AC 54 ms 29.86 MiB

import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline P = 998244353 p, g, ig = 998244353, 3, 332748118 W = [pow(g, (p - 1) >> i, p) for i in range(24)] iW = [pow(ig, (p - 1) >> i, p) for i in range(24)] def convolve(a, b): def fft(f): for l in range(k, 0, -1): d = 1 << l - 1 U = [1] for i in range(d): U.append(U[-1] * W[l] % p) for i in range(1 << k - l): for j in range(d): s = i * 2 * d + j t = s + d f[s], f[t] = (f[s] + f[t]) % p, U[j] * (f[s] - f[t]) % p def ifft(f): for l in range(1, k + 1): d = 1 << l - 1 U = [1] for i in range(d): U.append(U[-1] * iW[l] % p) for i in range(1 << k - l): for j in range(d): s = i * 2 * d + j t = s + d f[s], f[t] = (f[s] + f[t] * U[j]) % p, (f[s] - f[t] * U[j]) % p n0 = len(a) + len(b) - 1 k = (n0).bit_length() n = 1 << k a = a + [0] * (n - len(a)) b = b + [0] * (n - len(b)) fft(a), fft(b) for i in range(n): a[i] = a[i] * b[i] % p ifft(a) invn = pow(n, p - 2, p) for i in range(n0): a[i] = a[i] * invn % p del a[n0:] return a def Tonelli_Shanks(n, p = P): if pow(n, (p-1) // 2, p) == -1: return -1 if p % 4 == 3: a = pow(n, (p+1) // 4, p) return min(a, p - a) q = p - 1 s = 0 while q % 2 == 0: q //= 2 s += 1 for z in range(1, p): if pow(z, (p-1) // 2, p) != 1: break m = s c = pow(z, q, p) t = pow(n, q, p) r = pow(n, (q+1) // 2, p) while 1: if t == 0: return 0 if t == 1: return min(r, p - r) for i in range(1, m): if pow(t, 1 << i, p) == 1: break if m - i <= 0: return -1 b = pow(c, 1 << m-i-1, p) m = i c = b ** 2 % p t = t * b ** 2 % p r = r * b % p class fps(): def __init__(self, a, m = 10**6): if type(a) == int: self.len = 1 self.f = [a] else: self.len = len(a) self.f = a def __neg__(self): l = [0] * self.len for i, a in enumerate(self.f): l[i] = P - a if a else 0 return self.__class__(l) def aaafirst(self, n): return self.__class__(self.f[:n]) def __add__(self, other): if type(other) == int: return self + self.__class__([other]) if self.len > other.len: l = self.f[:] for i, a in enumerate(other.f): l[i] += a if l[i] >= P: l[i] -= P else: l = other.f[:] for i, a in enumerate(self.f): l[i] += a if l[i] >= P: l[i] -= P return self.__class__(l) def __sub__(self, other): if type(other) == int: return self - self.__class__([other]) l = self.f[:] + [0] * (other.len - self.len) for i, a in enumerate(other.f): l[i] -= a if l[i] < 0: l[i] += P return self.__class__(l) def __rsub__(self, other): return self.__class__([other]) - self def __mul__(self, other): if type(other) == int: l = self.f[:] for i in range(self.len): l[i] = l[i] * other % P return self.__class__(l) else: return self.__class__(convolve(self.f, other.f)) def __rmul__(self, other): l = self.f[:] for i in range(self.len): l[i] = l[i] * other % P return self.__class__(l) def inv(self, deg = -1): f = self.f[:] assert f[0] n = self.len if deg < 0: deg = n ret = __class__([pow(self.f[0], P - 2, P)]) i = 1 while i < deg: ret = (ret * (2 - ret * self[:i*2]))[:i*2] i <<= 1 return ret[:deg] def __truediv__(self, other, deg = -1): if type(other) == int: iv = pow(other, P - 2, P) l = self.f[:] for i in range(self.len): l[i] = l[i] * iv % P return self.__class__(l) else: if deg < 0: deg = max(self.len, other.len) return (self * other.inv(deg))[:deg] def sqrt(self): if self.f[0] == 0: for k, a in enumerate(self.f): if a: break else: return self.__class__([0] * self.len) if k & 1: return None sq = self.__class__(self.f[k:] + [0] * (k//2)).sqrt() if not sq: return None return fps([0] * (k//2) + sq.f) ts = Tonelli_Shanks(self.f[0]) if ts < 0: return None deg = self.len a = self.__class__([ts]) i = 1 while i < deg: a += self[i*2].__truediv__(a) a /= 2 i <<= 1 return a def f2e(self): f = self.f[:] for i, a in enumerate(f): f[i] = a * fainv[i] % P return self.__class__(f) def e2f(self): f = self.f[:] for i, a in enumerate(f): f[i] = a * fa[i] % P return self.__class__(f) def differentiate(self): f = self.f[:] for i, a in enumerate(f): f[i] = a * i % P f = f[1:] + [0] return self.__class__(f) def integrate(self): f = self.f[:] for i, a in enumerate(f): f[i] = a * fainv[i+1] % P * fa[i] % P f = [0] + f[:-1] return self.__class__(f) def log(self, deg = -1): return (self.differentiate().__truediv__(self, deg)).integrate() def exp(self, deg = -1): assert self.f[0] == 0 if deg < 0: deg = self.len a = self.__class__([1]) i = 1 while i < deg: a = (a * (self[:i*2] + 1 - a.log(i * 2)))[:i*2] i <<= 1 return a[:deg] def __pow__(self, n, deg = -1): if deg < 0: deg = self.len if self.f[0] == 0: assert n >= 0 for i, a in enumerate(self.f): if a: if i * n >= deg: return self.__class__([0] * deg) return self.__class__([0] * (i * n) + pow(self.__class__(self.f[i:]), n, deg - i * n).f) else: return self.__class__([0] * deg) if self.f[0] != 1: a = self.f[0] return pow(self / a, n, deg) * pow(a, n, P) return (self.log(deg) * n).exp(deg) def taylor_shift(self, c): deg = self.len L = [] a = 1 for i in range(deg): L.append(a * fainv[i] % P) a = a * c % P L = L[::-1] # return self.__class__((self.e2f() * self.__class__(L)).f[deg-1:]).f2e() return (self.e2f() * self.__class__(L))[deg-1:].f2e() def __getitem__(self, s): return self.__class__(self.f[s]) def __str__(self): l = [] for a in self.f: l.append(str(a)) return " ".join(l) N, C = map(int, input().split()) nn = N * 2 fa = [1] * (nn+1) fainv = [1] * (nn+1) for i in range(nn): fa[i+1] = fa[i] * (i+1) % P fainv[-1] = pow(fa[-1], P-2, P) for i in range(nn)[::-1]: fainv[i] = fainv[i+1] * (i+1) % P f = fps([int(a) for a in input().split()]) print(f.taylor_shift(C))