Submit Info #14041

Problem Lang User Status Time Memory
Partition Function pypy3 toyuzuko AC 5308 ms 173.54 MiB

ケース詳細
Name Status Time Memory
0_00 AC 42 ms 29.32 MiB
100000_00 AC 1152 ms 107.09 MiB
10000_00 AC 176 ms 37.34 MiB
1000_00 AC 80 ms 30.38 MiB
100_00 AC 55 ms 29.62 MiB
1_00 AC 44 ms 29.35 MiB
200000_00 AC 2447 ms 145.61 MiB
300000_00 AC 5271 ms 150.84 MiB
400000_00 AC 5308 ms 156.88 MiB
500000_00 AC 5270 ms 173.54 MiB
example_00 AC 36 ms 29.37 MiB

class FormalPowerSeries(): def __init__(self, n, arr=[], mod=998244353, root=3): self.n = n self.arr = arr + [0] * (n - len(arr)) self.mod = mod self.root = root @staticmethod def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1: a0, a1 = a1, a0 - c0 // c1 * a1 b0, b1 = b1, b0 - c0 // c1 * b1 c0, c1 = c1, c0 % c1 return c0, a0, b0 @staticmethod def modinv(x, mod): c, a, b = FormalPowerSeries.ex_euclid(x, mod) return a % mod @staticmethod def tonelli_shanks(n, p): #n<p if n == 0: return 0 if n == 1: return 1 if pow(n, (p - 1)//2, p) != 1: return -1 q, s = p - 1, 0 while q % 2 == 0: q //= 2 s += 1 z = 1 while pow(z, (p - 1)//2, p) != p - 1: z += 1 m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1)//2, p) while t != 1: k = 1 while pow(t, 2**k, p) != 1: k += 1 x = pow(c, pow(2, m - k - 1, p - 1), p) m = k c = (x * x) % p t = (t * c) % p r = (r * x) % p if r * r % p != n: return -1 return r def resize(self, n): res = FormalPowerSeries(n, [], self.mod) for i in range(min(n, self.n)): res.arr[i] = self.arr[i] return res def add(self, other): res = FormalPowerSeries(self.n, [], self.mod) for i in range(self.n): res.arr[i] = self.arr[i] + other.arr[i] res.arr[i] %= self.mod return res def subtract(self, other): res = FormalPowerSeries(self.n, [], self.mod) for i in range(self.n): res.arr[i] = self.arr[i] - other.arr[i] res.arr[i] %= self.mod return res def times(self, k): res = FormalPowerSeries(self.n, [], self.mod) for i in range(self.n): res.arr[i] = self.arr[i] * k % self.mod return res def multiply(self, other): res = FormalPowerSeries(self.n, [], self.mod) fmt = FastModuloTransform(self.n * 2, self.mod, self.root) cv = fmt.convolute(self.arr, other.arr) for i in range(self.n): res.arr[i] = cv[i] return res def square(self): res = FormalPowerSeries(self.n, [], self.mod) fmt = FastModuloTransform(self.n * 2, self.mod, self.root) cv = fmt.autocorrelation(self.arr) for i in range(self.n): res.arr[i] = cv[i] return res def inverse(self): #f[0] != 0 r = pow(self.arr[0], self.mod - 2, self.mod) m = 1 res = FormalPowerSeries(m, [r], self.mod) while m < self.n: m *= 2 res = res.resize(m) res = res.times(2).subtract(self.resize(m).multiply(res.square())) res = res.resize(self.n) return res def divide(self, other): res = self.multiply(other.inverse()) return res def differentiate(self): res = FormalPowerSeries(self.n, [], self.mod) for i in range(self.n - 1): res.arr[i] = self.arr[i + 1] * (i + 1) % self.mod return res def integrate(self): res = FormalPowerSeries(self.n, [], self.mod) for i in range(self.n - 1): res.arr[i + 1] = self.arr[i] * FormalPowerSeries.modinv(i + 1, self.mod) % self.mod return res def log(self): #f[0] == 1 res = self.differentiate().divide(self).integrate() return res def exp(self): #f[0] == 0 res = FormalPowerSeries(1, [1], self.mod) g = FormalPowerSeries(1, [1], self.mod) q = self.differentiate() m = 1 while m < self.n: m *= 2 g = g.times(2).subtract(res.multiply(g.square())) g = g.resize(m) res = res.resize(m) w = q.resize(m).add(g.multiply(res.differentiate().subtract(res.multiply(q.resize(m))))) res = res.add(res.multiply(self.resize(m).subtract(w.integrate()))) res = res.resize(self.n) return res def sqrt_(self): #f[0] != 0 s = FormalPowerSeries.tonelli_shanks(self.arr[0], self.mod) if s == -1: return m = 1 res = FormalPowerSeries(m, [s], self.mod) while m < self.n: m *= 2 res = res.resize(m) res = res.add(self.resize(m).divide(res)).times(FormalPowerSeries.modinv(2, self.mod)) res = res.resize(self.n) return res def sqrt(self): for i in range(self.n): if self.arr[i] != 0: d = i break else: return FormalPowerSeries(self.n, [], self.mod) if d % 2 == 1: return s = FormalPowerSeries.tonelli_shanks(self.arr[d], self.mod) if s == -1: return res = FormalPowerSeries(self.n, [], self.mod) g = FormalPowerSeries(self.n, self.arr[d:], self.mod) g = g.times(FormalPowerSeries.modinv(self.arr[d], self.mod)).sqrt_() if g is None: return g = g.times(s) for i in range(self.n - d + 1): if d // 2 + i >= self.n: break res.arr[d // 2 + i] = g.arr[i] return res def power(self, k): for i in range(self.n): if self.arr[i] != 0: d = i break else: return FormalPowerSeries(self.n, [], self.mod) res = FormalPowerSeries(self.n, [], self.mod) p = self.arr[d] g = FormalPowerSeries(self.n, self.arr[d:], self.mod) g = g.times(FormalPowerSeries.modinv(p, self.mod)) g = g.log().times(k).exp() for i in range(self.n): if d * k + i >= self.n: break res.arr[d * k + i] = g.arr[i] res = res.times(pow(p, k, self.mod)) return res @staticmethod def bernoulli(n, mod): f = Factorial(n + 1, mod) res = FormalPowerSeries(n, [1], mod) arr = [f.inv[i + 1] for i in range(n)] expx_1 = FormalPowerSeries(n, arr, mod) res = res.divide(expx_1) return [res.arr[i] * f.fct[i] % mod for i in range(n)] @staticmethod def partition(n, mod): res = FormalPowerSeries(n, [], mod) for i in range(-n, n + 1): k = i * (3 * i - 1) // 2 if k >= n: continue if i % 2 == 0: res.arr[k] = 1 else: res.arr[k] = mod - 1 res = res.inverse() return [res.arr[i] for i in range(n)] class FastModuloTransform(): def __init__(self, n, mod=998244353, root=3): self.h = (n - 1).bit_length() self.n = 2**self.h self.mod = mod self.omega = pow(root, (mod - 1) // self.n, mod) self.rev = pow(self.omega, mod - 2, mod) def _bit_reverse_(self, A): n = self.n m = self.n // 2 i = 0 for j in range(0, m, 2): if j < i: A[i], A[j] = A[j], A[i] A[i + m + 1], A[j + m + 1] = A[j + m + 1], A[i + m + 1] A[i + 1], A[j + m] = A[j + m], A[i + 1] k = m // 2 i ^= k while k > i: k //= 2 i ^= k return A def _fmt_(self, A, base): halfpow = pow(base, self.n // 2, self.mod) n = self.n m = 1 while n > 1: n //= 2 w = pow(base, n, self.mod) k = 1 for j in range(m): for i in range(j, self.n, 2 * m): u = A[i] v = (A[i + m] * k) % self.mod A[i] = (u + v) % self.mod A[i + m] = (u + v * halfpow) % self.mod k = (k * w) % self.mod m *= 2 return A def fmt(self, f): A = f + [0] * (self.n - len(f)) self._bit_reverse_(A) F = self._fmt_(A, self.omega) return F def ifmt(self, F): A = F + [0] * (self.n - len(F)) self._bit_reverse_(A) nrev = pow(self.n, self.mod - 2, self.mod) f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)] return f def convolute(self, f, g): F = self.fmt(f) G = self.fmt(g) H = [(s * t) % self.mod for s, t in zip(F, G)] h = self.ifmt(H) return h def autocorrelation(self, f): F = self.fmt(f) H = [(s * s) % self.mod for s in F] h = self.ifmt(H) return h class Factorial(): def __init__(self, n, mod): self.mod = mod self.fct = [0 for _ in range(n + 1)] self.inv = [0 for _ in range(n + 1)] self.fct[0] = 1 self.inv[0] = 1 for i in range(n): self.fct[i + 1] = self.fct[i] * (i + 1) % mod self.inv[n] = pow(self.fct[n], mod - 2, mod) for i in range(n)[::-1]: self.inv[i] = self.inv[i + 1] * (i + 1) % mod def fact(self, m): return self.fct[m] def invf(self, m): return self.inv[m] def perm(self, m, k): if m < k: return 0 return self.fct[m] * self.inv[m - k] % self.mod def comb(self, m, k): if m < k: return 0 return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod def hcmb(self, m, k): if m + k == 0: return 1 return self.comb(m + k - 1, k) MOD = 998244353 N = int(input()) print(*FormalPowerSeries.partition(N + 1, MOD))