Submit Info #28785

Problem Lang User Status Time Memory
Polynomial Interpolation pypy3 onakasuitacity AC 9454 ms 235.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 51 ms 29.76 MiB
example_01 AC 51 ms 29.73 MiB
max_random_00 AC 9454 ms 235.93 MiB
max_random_01 AC 9281 ms 228.93 MiB
random_00 AC 9132 ms 230.05 MiB
random_01 AC 7043 ms 193.97 MiB
random_02 AC 4667 ms 141.49 MiB

import sys input = lambda:sys.stdin.readline().rstrip() MOD = 998244353 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))) return _fmt([a * b % prime for a, b in zip(Ff, Fg)], inverse = True)[:len(f) + len(g) - 1] def inverse(f): g = [pow(f[0], MOD - 2, MOD)] d = 1 for _ in range(len(f).bit_length()): d <<= 1 h = [-v for v in convolve(f[:d], g)[:d]] h[0] += 2 g = convolve(g, h)[:d] return g[:len(f)] def differentiate(f): return [k * v % MOD for k, v in enumerate(f[1:], 1)] if len(f) > 1 else [0] def modulo(f, g): l = len(f) - len(g) + 1 if l <= 0: return f if len(g) <= 2048: q = [0] * l r = f[:] c_inv = pow(g[-1], MOD - 2, MOD) for i in range(l): q[~i] = c_inv * r[~i] q[~i] %= MOD for j in range(len(g)): r[~(i+j)] -= g[~j] * q[~i] r[~(i+j)] %= MOD return r[:max(len(g) - 1, 1)] q = convolve(f[:-l-1:-1], inverse(g[:-l-1:-1] + [0] * (l - len(g))))[l-1::-1] return [(a - b) % MOD for a, b in zip(f, convolve(g, q)[:len(g) - 1])] def resolve(): n = int(input()) N = 1 << (n - 1).bit_length() mul_tree = [[1] for _ in range(N * 2)] for i, x in enumerate(map(int, input().split())): mul_tree[i + N] = [-x, 1] for i in range(N - 1, 0, -1): mul_tree[i] = convolve(mul_tree[i * 2], mul_tree[i * 2 + 1]) mod_tree = [0] * (N * 2) mod_tree[1] = differentiate(mul_tree[1]) for i in range(2, N * 2): mod_tree[i] = modulo(mod_tree[i // 2], mul_tree[i]) for i, y in enumerate(map(int, input().split())): mod_tree[i + N][0] = y * pow(mod_tree[i + N][0], MOD - 2, MOD) % MOD for i in range(N - 1, 0, -1): mod_tree[i] = [(a + b) % MOD for a, b in zip(convolve(mul_tree[i * 2], mod_tree[i * 2 + 1]), convolve(mul_tree[i * 2 + 1], mod_tree[i * 2]))] print(*mod_tree[1]) resolve()