Submit Info #2651

Problem Lang User Status Time Memory
Bernoulli Number python3 maspy AC 1676 ms 161.92 MiB

ケース詳細
Name Status Time Memory
0_00 AC 195 ms 67.47 MiB
1_00 AC 194 ms 67.52 MiB
100_00 AC 195 ms 67.43 MiB
1000_00 AC 197 ms 67.47 MiB
10000_00 AC 220 ms 67.43 MiB
100000_00 AC 458 ms 78.89 MiB
200000_00 AC 813 ms 102.73 MiB
300000_00 AC 1568 ms 152.24 MiB
400000_00 AC 1611 ms 155.93 MiB
500000_00 AC 1676 ms 161.92 MiB
example_00 AC 195 ms 67.52 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 __truediv__(self,other): L = len(other) return (self * other.inv())[:L] 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.int64([x])) 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] 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 Bernoulli(N): A = Polynomial.ModFactInv[1:N+1].copy() f = Polynomial(A).inv() f.v *= Polynomial.ModFact[:len(f)]; f.v %= MOD return f N = int(read()) Bernoulli(N+1).print()