Submit Info #2629

Problem Lang User Status Time Memory
Inv of Formal Power Series python3 maspy AC 1610 ms 120.73 MiB

ケース詳細
Name Status Time Memory
example_00 AC 99 ms 14.16 MiB
max_random_00 AC 1610 ms 120.73 MiB
max_random_01 AC 1574 ms 120.56 MiB
max_random_02 AC 1571 ms 120.62 MiB
max_random_03 AC 1588 ms 120.60 MiB
max_random_04 AC 1575 ms 120.54 MiB
random_00 AC 1496 ms 113.16 MiB
random_01 AC 1529 ms 115.17 MiB
random_02 AC 242 ms 27.09 MiB
random_03 AC 1519 ms 114.36 MiB
random_04 AC 1401 ms 113.09 MiB

import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 998244353 class Polynomial: MOD = MOD fact = None fact_inv = None def __init__(self, array): assert array.dtype == np.int64 self.v = array def __getitem__(self,item): if type(item) == slice: return Polynomial(self.v[item]) else: return self.v[item] def __repr__(self): return 'Polynomial modulo {}\n'.format(Polynomial.MOD) + self.v.__repr__() def print(self, sep = ' '): print(sep.join(self.v.astype(str))) def __eq__(self,other): return np.all(self.v == other.v) def __len__(self): return len(self.v) def __add__(self, other): Ls = len(self.v); Lo = len(other.v) if Ls < Lo: Ls, Lo = Lo, Ls; self,other = other,self array = self.v.copy(); array[:Lo] += other.v; array[:Lo] %= Polynomial.MOD return Polynomial(array) def __iadd__(self, other): Ls = len(self.v); Lo = len(other.v) if Ls < Lo: self.resize(Lo) self.v[:Lo] += other.v; self.v %= Polynomial.MOD; return self def __sub__(self, other): Ls = len(self); Lo = len(other) if Ls < Lo: Ls, Lo = Lo, Ls; self,other = other,self array = self.v.copy(); array[:Lo] -= other.v; array[:Lo] %= Polynomial.MOD return Polynomial(array) def __isub__(self, other): Ls = len(self.v); Lo = len(other.v) if Ls < Lo: self.resize(Lo) self.v[:Lo] -= other.v; self.v %= Polynomial.MOD; return self def convolve(f, g): Lf = len(f); Lg = len(g); L = Lf + Lg - 1 fl = f & (1 << 15) - 1; fh = f >> 15 gl = g & (1 << 15) - 1; gh = g >> 15 if L < (1<<8): conv = lambda f,g: \ np.convolve(f,g) % Polynomial.MOD else: fft = np.fft.rfft; ifft = np.fft.irfft; fft_len = 1 << L.bit_length() conv = lambda f,g: \ np.rint(ifft(fft(f,fft_len) * fft(g,fft_len))[:L]).astype(np.int64) % Polynomial.MOD x = conv(fl, gl); z = conv(fh, gh); y = conv(fl+fh, gl+gh) return Polynomial((x + ((y - x - z) << 15) + (z << 30)) % Polynomial.MOD) def __mul__(self, other): return Polynomial.convolve(self.v, other.v) def resize(self,N): L = len(self.v); self.v = np.resize(self.v,N); self.v[L:] = 0; return self def inv(self): F = self; L = len(F); x = int(F[0]); assert x != 0 i = (L-1).bit_length(); N = 1 << i; F.resize(N) x = pow(x,MOD-2,MOD); R = Polynomial(np.array([x],np.int64)) n = 1 for _ in range(i): RF = (R * F[:n+n])[:n+n] RRF = (R * RF)[:n+n] R += R; R -= RRF n += n F.resize(L) return R[:L] N = int(readline()) f = Polynomial(np.array(read().split(),np.int64)) f.inv().print()