Submit Info #28424

Problem Lang User Status Time Memory
Stirling Number of the First Kind pypy3 onakasuitacity AC 5158 ms 227.26 MiB

ケース詳細
Name Status Time Memory
0_00 AC 60 ms 37.45 MiB
1_00 AC 62 ms 37.45 MiB
262143_00 AC 1512 ms 152.59 MiB
262144_00 AC 4202 ms 187.12 MiB
2_00 AC 55 ms 37.45 MiB
491519_00 AC 3029 ms 227.26 MiB
499999_00 AC 3086 ms 219.70 MiB
500000_00 AC 5158 ms 214.13 MiB
5000_00 AC 143 ms 48.07 MiB
example_00 AC 60 ms 37.49 MiB

import sys INF = 1 << 60 MOD = 998244353 sys.setrecursionlimit(2147483647) input = lambda:sys.stdin.readline().rstrip() prime = 998244353 root = 3 def _fmt(f, inverse = False): N = len(f) logN = (N - 1).bit_length() base = pow(root, (prime - 1) // N * (1 - 2 * inverse) % (prime - 1), prime) step = N for k in range(logN): step >>= 1 w = pow(base, step, prime) wj = 1 nf = [0] * N for j in range(1 << k): for i in range(1 << logN - k - 1): s, t = i + 2 * j * step, i + (2 * j + 1) * step ns, nt = i + j * step, i + j * step + (N >> 1) nf[ns], nf[nt] = (f[s] + f[t] * wj) % prime, (f[s] - f[t] * wj) % prime wj = (wj * w) % prime f = nf if inverse: N_inv = pow(N, prime - 2, prime) f = [a * N_inv % prime for a in f] return f def convolve(f, g): N = 1 << (len(f) + len(g) - 2).bit_length() Ff, Fg = _fmt(f + [0] * (N - len(f))), _fmt(g + [0] * (N - len(g))) fg = _fmt([a * b % prime for a, b in zip(Ff, Fg)], inverse = True) del fg[len(f) + len(g) - 1:] return fg class modfact(object): def __init__(self, n): fact, invfact = [1] * (n + 1), [1] * (n + 1) for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD invfact[n] = pow(fact[n], MOD - 2, MOD) for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD self._fact, self._invfact = fact, invfact def inv(self, n): return self._fact[n - 1] * self._invfact[n] % MOD if n < len(self._fact) else pow(n, MOD - 2, MOD) def fact(self, n): return self._fact[n] def invfact(self, n): return self._invfact[n] def comb(self, n, k): return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD if 0 <= k <= n else 0 def perm(self, n, k): return self._fact[n] * self._invfact[n - k] % MOD if 0 <= k <= n else 0 mf = modfact(500005) def shift(f, c): n = len(f) g = [mf.fact(i) * v for i, v in enumerate(f)][::-1] exp = [0] * n p = 1 for i in range(n): exp[i] = mf.invfact(i) * p % MOD p = p * c % MOD return [v * mf.invfact(i) % MOD for i, v in enumerate(convolve(g, exp)[n-1::-1])] def resolve(): n = int(input()) f = [1] base = [0, 1] for d in range(n.bit_length()): if n >> d & 1: f = convolve(f, shift(base, -(len(f) - 1))) base = convolve(base, shift(base, -(len(base) - 1))) print(*f) resolve()