Submit Info #28378

Problem Lang User Status Time Memory
Polynomial Taylor Shift pypy3 onakasuitacity AC 869 ms 214.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 49 ms 29.84 MiB
example_01 AC 50 ms 29.79 MiB
fft_killer_00 AC 859 ms 212.84 MiB
fft_killer_01 AC 852 ms 204.70 MiB
max_random_00 AC 863 ms 214.62 MiB
max_random_01 AC 869 ms 214.62 MiB
medium_00 AC 79 ms 31.45 MiB
medium_01 AC 82 ms 32.58 MiB
medium_02 AC 86 ms 32.70 MiB
medium_all_zero_00 AC 81 ms 31.52 MiB
medium_c_zero_00 AC 79 ms 31.57 MiB
random_00 AC 784 ms 175.13 MiB
random_01 AC 833 ms 208.94 MiB
random_02 AC 162 ms 69.08 MiB
small_00 AC 48 ms 29.84 MiB
small_01 AC 51 ms 29.84 MiB
small_02 AC 50 ms 29.84 MiB
small_03 AC 51 ms 29.82 MiB
small_04 AC 46 ms 29.83 MiB
small_05 AC 50 ms 29.84 MiB
small_06 AC 54 ms 29.78 MiB
small_07 AC 51 ms 29.76 MiB
small_08 AC 51 ms 29.78 MiB
small_09 AC 52 ms 29.83 MiB
small_10 AC 52 ms 29.82 MiB
small_11 AC 50 ms 29.85 MiB
small_12 AC 54 ms 29.86 MiB
small_13 AC 54 ms 29.84 MiB
small_14 AC 52 ms 29.84 MiB
small_15 AC 53 ms 29.85 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 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 def resolve(): n, c = map(int, input().split()) f = list(map(int, input().split())) mf = modfact(n) g = [mf.fact(i) * v for i, v in enumerate(f)][::-1] exp = [pow(c, i, MOD) * mf.invfact(i) % MOD for i in range(n)] res = convolve(g, exp)[n-1::-1] for i in range(n): res[i] = res[i] * mf.invfact(i) % MOD print(*res) resolve()