# Submit Info #2645

Problem Lang User Status Time Memory
Exp of Formal Power Series python3 maspy AC 8025 ms 198.36 MiB

ケース詳細
Name Status Time Memory
example_00 AC 197 ms 67.47 MiB
max_random_00 AC 7817 ms 182.73 MiB
max_random_01 AC 7774 ms 182.66 MiB
max_random_02 AC 7778 ms 182.70 MiB
max_random_03 AC 7902 ms 182.68 MiB
max_random_04 AC 8025 ms 184.66 MiB
random_00 AC 7771 ms 183.57 MiB
random_01 AC 7678 ms 198.36 MiB
random_02 AC 708 ms 74.65 MiB
random_03 AC 7781 ms 185.10 MiB
random_04 AC 7719 ms 180.03 MiB

import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 998244353 def cumprod(A, MOD = MOD): L = len(A); Lsq = int(L**.5+1) A = np.resize(A, Lsq**2).reshape(Lsq,Lsq) for n in range(1,Lsq): A[:,n] *= A[:,n-1]; A[:,n] %= MOD for n in range(1,Lsq): A[n] *= A[n-1,-1]; A[n] %= MOD return A.ravel()[:L] def make_fact(U, MOD = MOD): x = np.arange(U, dtype = np.int64); x[0] = 1 fact = cumprod(x, MOD) x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD) fact_inv = cumprod(x, MOD)[::-1] return fact,fact_inv class Polynomial: MOD = MOD ModFact, ModFactInv = make_fact(10**6,MOD) ModInv = np.zeros(10**6, np.int64) ModInv[1:] = ModFactInv[1:] * ModFact[:-1] % MOD def __init__(self, array): assert array.dtype == np.int64 self.v = array @classmethod def zeros(cls, N): return cls(np.zeros(N,np.int64)) @classmethod def ones(cls, N): return cls(np.ones(N,np.int64)) @classmethod def arange(cls,N): return cls(np.arange(N,dtype=np.int64)) 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 __mul__(self, other): f = self.v; g = other.v Lf = len(f); Lg = len(g); L = Lf + Lg - 1 if not Lf: return Polynomial.zeros(1) if not Lg: return Polynomial.zeros(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 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) n = 1 f = Polynomial.ones(1); g = Polynomial.ones(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] def differentiate(self): L = len(self) if L == 1: return Polynomial.zeros(1) return Polynomial(self.v[1:] * np.arange(1,L,dtype=np.int64) % MOD) def integrate(self): L = len(self) A = np.zeros(L+1,np.int64) A[1:] = self.v * Polynomial.ModInv[1:L+1] % MOD return Polynomial(A) def exp(self): # http://www.csd.uwo.ca/~eschost/publications/BoSc09-final.pdf h = self; L = len(h) assert h[0] == 0 dh = h.differentiate() i = (L-1).bit_length(); N = 1 << i; h.resize(N) f = Polynomial.ones(1); g = Polynomial.ones(1) m = 1 for _ in range(i): fg = (f * g)[:m]; fgg = (fg * g)[:m] g+= g; g -= fgg q = dh[:m-1] df = f.differentiate() df -= (f * q)[:m+m-1] df *= g; w = df[:m+m-1] + q w = w.integrate() f = (h - w + Polynomial.ones(1)) * f; f = f[:m+m] m += m return f[:L] N = int(readline()) f = Polynomial(np.int64(read().split())) f.exp().print()