Submit Info #32967

Problem Lang User Status Time Memory
Partition Function pypy3 Eki1009 AC 911 ms 145.71 MiB

ケース詳細
Name Status Time Memory
0_00 AC 51 ms 29.90 MiB
100000_00 AC 269 ms 70.57 MiB
10000_00 AC 105 ms 33.59 MiB
1000_00 AC 82 ms 31.45 MiB
100_00 AC 62 ms 30.84 MiB
1_00 AC 58 ms 29.86 MiB
200000_00 AC 451 ms 106.02 MiB
300000_00 AC 817 ms 144.78 MiB
400000_00 AC 808 ms 145.71 MiB
500000_00 AC 911 ms 139.19 MiB
example_00 AC 49 ms 29.84 MiB

mod = 998244353 sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497) sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951) I_li = [] def inv_gcd(a, b): a %= b if a == 0: return b, 0 s, t = b, a m0, m1 = 0, 1 while t: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += b // s return s, m0 def inv_mod(x): return inv_gcd(x, mod)[1] def butterfly(a_li): n = len(a_li) h = (n - 1).bit_length() for ph in range(1, h + 1): w = 1 << (ph - 1) p = 1 << (h - ph) now = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a_li[i + offset] r = a_li[i + offset + p] * now a_li[i + offset] = (l + r) % mod a_li[i + offset + p] = (l - r) % mod now *= sum_e[(~s & -~s).bit_length() - 1] now %= mod def butterfly_inv(a_li): n = len(a_li) h = (n - 1).bit_length() for ph in range(h, 0, -1): w = 1 << (ph - 1) p = 1 << (h - ph) inow = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a_li[i + offset] r = a_li[i + offset + p] a_li[i + offset] = (l + r) % mod a_li[i + offset + p] = (mod + l - r) * inow % mod inow *= sum_ie[(~s & -~s).bit_length() - 1] inow %= mod def convolution(_a_li, _b_li): a_li = _a_li.copy() b_li = _b_li.copy() n = len(a_li) m = len(b_li) if not n or not m: return [] if min(n, m) <= 60: if n < m: n, m = m, n a_li, b_li = b_li, a_li res = [0] * (n + m - 1) for i in range(n): for j in range(m): res[i + j] += a_li[i] * b_li[j] res[i + j] %= mod return res z = 1 << (n + m - 2).bit_length() a_li += [0] * (z - n) b_li += [0] * (z - m) butterfly(a_li) butterfly(b_li) for i in range(z): a_li[i] *= b_li[i] a_li[i] %= mod butterfly_inv(a_li) a_li = a_li[:n + m - 1] iz = inv_mod(z) for i in range(n + m - 1): a_li[i] *= iz a_li[i] %= mod return a_li def autocorrelation(_a_li): a_li = _a_li.copy() n = len(a_li) if not n: return [] if n <= 60: res = [0] * (n + n - 1) for i in range(n): for j in range(n): res[i + j] += a_li[i] * a_li[j] res[i + j] %= mod return res z = 1 << (n + n - 2).bit_length() a_li += [0] * (z - n) butterfly(a_li) for i in range(z): a_li[i] *= a_li[i] a_li[i] %= mod butterfly_inv(a_li) a_li = a_li[:n + n - 1] iz = inv_mod(z) for i in range(n + n - 1): a_li[i] *= iz a_li[i] %= mod return a_li class formal_power_series: def __init__(self, poly=[]): self.poly = [p % mod for p in poly] def __getitem__(self, key): if isinstance(key, slice): res = self.poly[key] return formal_power_series(res) else: if key < 0: raise IndexError("list index out of range") if key >= len(self.poly): return 0 else: return self.poly[key] def __setitem__(self, key, value): if key < 0: raise IndexError("list index out of range") if key >= len(self.poly): self.poly += [0] * (key - len(self.poly) + 1) self.poly[key] = value % mod def __len__(self): return len(self.poly) def times(self, n): n %= mod res = [p * n for p in self.poly] return formal_power_series(res) def __pos__(self): return self def __neg__(self): return self.times(-1) def __add__(self, other): if other.__class__ == formal_power_series: s = len(self) t = len(other) n = min(s, t) res = [self.poly[i] + other.poly[i] for i in range(n)] if s >= t: res += self.poly[t:] else: res += other.poly[s:] return formal_power_series(res) else: self.poly[0] += other self.poly[0] %= mod return self def __radd__(self, other): return self + other def __sub__(self, other): return self + (-other) def __rsub__(self, other): return (-self) + other def __mul__(self, other): if other.__class__ == formal_power_series: res = convolution(self.poly, other.poly) return formal_power_series(res) else: return self.times(other) def __rmul__(self, other): return self.times(other) def square(self): res = autocorrelation(self.poly) return formal_power_series(res) def inv(self, deg=-1): r = inv_mod(self.poly[0]) if deg == -1: deg = len(self) - 1 m = 1 res = formal_power_series([r]) while m <= deg: m <<= 1 t_li = (self[:m] * res.square()[:m])[:m] res = res * 2 - t_li return res[:deg + 1] #P/Q def __truediv__(self, other): if other.__class__ == formal_power_series: return (self * other.inv()) else: return self * inv_mod(other) def __rtruediv__(self, other): return other * self.inv() #P,Qを多項式として見たときのPをQで割った商を求める def __floordiv__(self, other): if other.__class__ == formal_power_series: if len(self) < len(other): return formal_power_series() else: m = len(self) - len(other) + 1 res = (self[-1:-m-1:-1] * other[::-1].inv(m))[m-1::-1] return res else: return self * inv_mod(other) def __rfloordiv__(self, other): return other * self.inv() def __mod__(self, other): if len(self) < len(other): return self[:] else: res = self[:len(other) - 1] - ((self // other) * other)[:len(other) - 1] return res def differentiate(self): res = [k * p for k, p in enumerate(self.poly[1:], 1)] return formal_power_series(res) def integrate(self): while len(I_li) <= len(self): I_li.append(inv_mod(len(I_li))) res = [0] + [I_li[k] * p for k, p in enumerate(self.poly, 1)] return formal_power_series(res) def log(self, deg=-1): if deg == -1: deg = len(self) - 1 return (self.differentiate() / self)[:deg].integrate() def exp(self, deg=-1): if deg == -1: deg = len(self) - 1 res = formal_power_series([1]) g_li = formal_power_series([1]) df = self.differentiate() m = 1 while m <= deg: g_li = g_li * 2 - (res * g_li.square())[:m] m <<= 1 dft = df[:m] w_li = dft + (g_li * (res.differentiate() - (res * dft)[:m]))[:m] res += (res * (self[:m] - w_li.integrate()[:m]))[:m] return res[:deg + 1] def __pow__(self, n, deg=-1): if deg == -1: deg = len(self) + 1 m = abs(n) for d, p in enumerate(self.poly): if p: break else: return formal_power_series() if d * m >= len(self): return formal_power_series() g_li = self[d:] g_li = ((g_li * inv_mod(p)).log() * m).exp() * pow(p, m, mod) res = formal_power_series([0] * (d * m) + g_li.poly) if n >= 0: return res[:deg + 1] else: return res.inv()[:deg + 1] #各p_i(0<=i<m)についてf(p_i)を求める def multipoint_evaluation(self, P): m = len(P) size = 1 << (m - 1).bit_length() g_li = [formal_power_series([1]) for _ in range(2 * size)] for i in range(m): g_li[size + i] = formal_power_series([-P[i], 1]) for i in range(size - 1, 0, -1): g_li[i] = g_li[2 * i] * g_li[2 * i + 1] g_li[1] = self % g_li[1] for i in range(2, size + m): g_li[i] = g_li[i >> 1] % g_li[i] res = [g_li[i][0] for i in range(size, size + m)] return res #[x^n]P/Qを求める def poly_coef(Q, P, n): while n: R = [0] * len(Q.poly) for i, q in enumerate(Q.poly): if i & 1: R[i] = -q else: R[i] = q R = formal_power_series(R) P = P * R Q = Q * R if n & 1: P = P[1::2] else: P = P[::2] Q = Q[::2] n >>= 1 return P[0] def subset_sum(a_li, limit): C = [0] * (limit + 1) for a in a_li: C[a] += 1 while len(I_li) <= limit: I_li.append(inv_mod(len(I_li))) res = formal_power_series() for i in range(1, limit + 1): for k in range(1, limit // i + 1): j = i * k res[j] += ((k & 1) * 2 - 1) * C[i] * I_li[k] return res.exp(limit).poly def partition_function(n): res = formal_power_series() t = int((1 + 24 * n) ** 0.5) for i in range((-t) // 6 + 1, (1 + t) // 6 + 1): k = i * (3 * i - 1) // 2 res[k] = 1 - (i & 1) * 2 return res.inv(n).poly import sys input = sys.stdin.readline n = int(input()) ans = partition_function(n) print(*ans)