Problem:


Score : 100 points

Problem Statement

You are given two integer arrays a_0, a_1, ..., a_{N - 1} and b_0, b_1, ..., b_{M - 1}. Calculate the array c_0, c_1, ..., c_{(N - 1) + (M - 1)}, defined by c_i = \sum_{j = 0}^i a_j b_{i - j} \bmod 998244353.

Constraints

1 \leq N, M \leq 524288

0 \leq a_i, b_i < 998244353

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{M-1}

Output

Print the answer in the following format:

c_0 c_1 ... c_{(N - 1) + (M - 1)}

Sample Input 1

4 5
1 2 3 4
5 6 7 8 9

Sample Output 1

5 16 34 60 70 70 59 36

Sample Input 2

1 1
10000000
10000000

Sample Output 2

871938225



Sample input:
4 5
1 2 3 4
5 6 7 8 9


Sample output:
5 16 34 60 70 70 59 36

Submission status: Runtime Error

Solution code:
MOD = 998244353
ROOT = 3

class Convolution_998244353():
    def __init__(self):
        self.first1 = True
        self.first2 = True
        self.sum_e = [0] * 30
        self.sum_ie = [0] * 30

    def inv_gcd(self, a, b):
        a %= b
        if a == 0: return b, 0
        s = b
        t = a
        m0 = 0
        m1 = 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 butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first1:
            self.first1 = False
            es = [0] * 30
            ies = [0] * 30
            m = MOD - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(ROOT, m >> cnt2, MOD)
            ie = pow(e, MOD - 2, MOD)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= MOD
                ie *= ie
                ie %= MOD
            now = 1
            for i in range(cnt2 - 2):
                self.sum_e[i] = es[i] * now % MOD
                now *= ies[i]
                now %= MOD
        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 = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (l - r) % MOD
                now *= self.sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD

    def butterfly_inv(self, arr):
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first2:
            self.first2 = False
            es = [0] * 30
            ies = [0] * 30
            m = MOD - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(ROOT, m >> cnt2, MOD)
            ie = pow(e, MOD - 2, MOD)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= MOD
                ie *= ie
                ie %= MOD
            now = 1
            for i in range(cnt2 - 2):
                self.sum_ie[i] = ies[i] * now % MOD
                now *= es[i]
                now %= MOD
        for ph in range(1, h + 1)[::-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 = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (MOD + l - r) * inow % MOD
                inow *= self.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD

    def convolution(self, a, b):
        n = len(a)
        m = len(b)
        if not n or not m: return []
        if min(n, m) <= 50:
            if n < m:
                n, m = m, n
                a, b = b, a
            res = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    res[i + j] += a[i] * b[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.butterfly(a)
        self.butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

    def autocorrelation(self, a):
        n = len(a)
        if not n: return []
        if n <= 50:
            res = [0] * (2 * n - 1)
            for i in range(n):
                for j in range(n):
                    res[i + j] += a[i] * a[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (2 * n - 2).bit_length()
        a += [0] * (z - n)
        self.butterfly(a)
        for i in range(a):
            a[i] *= a[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:2 * n - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(2 * n - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

cv = Convolution_998244353()

print(*cv.convolution(A, B))

Submission status: Runtime Error

Solution code:
MOD = 998244353
ROOT = 3

class Convolution_998244353():
    def __init__(self):
        self.first1 = True
        self.first2 = True
        self.sum_e = [0] * 30
        self.sum_ie = [0] * 30

    def inv_gcd(self, a, b):
        a %= b
        if a == 0: return b, 0
        s = b
        t = a
        m0 = 0
        m1 = 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 butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first1:
            self.first1 = False
            es = [0] * 30
            ies = [0] * 30
            m = MOD - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(ROOT, m >> cnt2, MOD)
            ie = pow(e, MOD - 2, MOD)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= MOD
                ie *= ie
                ie %= MOD
            now = 1
            for i in range(cnt2 - 2):
                self.sum_e[i] = es[i] * now % MOD
                now *= ies[i]
                now %= MOD
        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 = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (l - r) % MOD
                now *= self.sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD

    def butterfly_inv(self, arr):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first2:
            self.first2 = False
            es = [0] * 30
            ies = [0] * 30
            m = MOD - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(ROOT, m >> cnt2, MOD)
            ie = pow(e, MOD - 2, MOD)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= MOD
                ie *= ie
                ie %= MOD
            now = 1
            for i in range(cnt2 - 2):
                self.sum_ie[i] = ies[i] * now % MOD
                now *= es[i]
                now %= MOD
        for ph in range(1, h + 1)[::-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 = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (MOD + l - r) * inow % MOD
                inow *= self.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD

    def convolution(self, a, b):
        n = len(a)
        m = len(b)
        if not n or not m: return []
        if min(n, m) <= 50:
            if n < m:
                n, m = m, n
                a, b = b, a
            res = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    res[i + j] += a[i] * b[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.butterfly(a)
        self.butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

    def autocorrelation(self, a):
        n = len(a)
        if not n: return []
        if n <= 50:
            res = [0] * (2 * n - 1)
            for i in range(n):
                for j in range(n):
                    res[i + j] += a[i] * a[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (2 * n - 2).bit_length()
        a += [0] * (z - n)
        self.butterfly(a)
        for i in range(a):
            a[i] *= a[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:2 * n - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(2 * n - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

cv = Convolution_998244353()

print(*cv.convolution(A, B))

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.fft import fft
from numpy.fft import ifft



class Convolution:

  def __init__(s, MOD):
    s.MOD = MOD
    s.PrimitiveRoot = s.primitive_root(MOD)
    s._BIT_TABLE = [0] * 64
    _BIT_HASH = 0x03F566ED27179461
    for i in range(64):
      s._BIT_TABLE[_BIT_HASH >> 58] = i
      _BIT_HASH <<= 1
      _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

  def convolution(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    c = s.convolutionModInt(a, b)
    return c

  def convolutionModInt(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    if min(n, m) <= 60:
      if n < m:
        n, m = m, n
        a, b = b, a
      ans = [0] * (n + m - 1)
      for i in range(n):
        for j in range(m):
          ans[i + j] += a[i] * b[j] % s.MOD
      return ans
    z = 1 << s.ceil_pow2(n + m - 1)
    a = a + [0] * (z - n)
    a = s.butterfly(a)
    b = b + [0] * (z - m)
    b = s.butterfly(b)
    for i in range(z): a[i] = a[i] * b[i] % s.MOD
    a = s.butterfly_inv(a)
    iz = pow(z, s.MOD - 2, s.MOD)
    for i in range(n + m - 1): a[i] = a[i] * iz % s.MOD
    return a[:n + m - 1]

  def butterfly(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_e = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_e[i] = es[i] * now % s.MOD
        now = now * ies[i] % s.MOD
    for ph in range(1, h + 1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      now = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * now % s.MOD
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (l - r) % s.MOD
        now = now * sum_e[s.bsf(~ss)] % s.MOD
    return a

  def butterfly_inv(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_ie = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_ie[i] = ies[i] * now % s.MOD
        now = now * es[i] % s.MOD
    for ph in range(h, 0, -1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      inow = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (s.MOD + l - r) * inow % s.MOD
        inow = inow * sum_ie[s.bsf(~ss)] % s.MOD
    return a

  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

  def bsf(s, n):
    if n == 0: return 64
    x = n
    y = x & -x
    i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
    return s._BIT_TABLE[i]

  def prime(s, x):
    L = []
    for i in range(1, int(x ** (1 / 2)) + 1):
      if x % i == 0:
        L.append(i)
        if i != x // i:
          L.append(x // i)
    L.sort()
    return L

  def primitive_root(s, x):
    L = s.prime(x - 1)[:-1]
    a = 2
    i = 0
    k = len(L)
    while i != k:
      if pow(a, L[i], x) == 1:

        a += 1
        i = 0
      else:
        i += 1
    return a


N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 998244353
conv = Convolution(MOD)
ans = conv.convolution(a, b)
print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
mod = 1012924417
primitive_root = 5
roots = [pow(primitive_root, (mod-1)>>i, mod) for i in range(22)]
inv_roots = [pow(root, mod-2, mod) for root in roots]

def ntt(A, n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m])%mod, (A[s+j]-A[s+j+m])*w%mod
                w *= roots[n-i]
                w %= mod

def intt(A, n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m]*w)%mod, (A[s+j]-A[s+j+m]*w)%mod
                w *= inv_roots[i+1]
                w %= mod
    inv = pow((mod+1)//2, n, mod)
    for i in range(1<<n):
        A[i] *= inv
        A[i] %= mod

def convolution(A, B):
    la = len(A)
    lb = len(B)
    deg = la + lb - 2
    n = deg.bit_length()
    N = 1<<n
    A += [0]*(N-la)
    B += [0]*(N-lb)
    ntt(A, n)
    ntt(B, n)
    A = [a*b%mod for a, b in zip(A, B)]
    intt(A, n)
    return A[:deg+1]


import sys
input = sys.stdin.readline
n = int(input())
A, B = [0], [0]
for _ in range(n):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
C = convolution(A, B)
print(*C[1:], sep="\n")

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.fft import fft
from numpy.fft import ifft
import sympy

_BIT_TABLE = [0] * 64
_BIT_HASH = 0x03F566ED27179461
for i in range(64):
  _BIT_TABLE[_BIT_HASH >> 58] = i
  _BIT_HASH <<= 1
  _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

def convolution(a, b, MOD):
  ModInt.set_mod(MOD)
  n, m = len(a), len(b)
  if not n or not m: return []
  a2, b2 = [0] * n, [0] * m
  for i in range(n):
    a2[i] = ModInt(a[i])
  for i in range(m):
    b2[i] = ModInt(b[i])
  c2 = convolutionModInt(a2, b2)
  c = [0] * (n + m - 1)
  for i in range(n + m - 1):
    c[i] = c2[i].val()
  return c

def convolutionModInt(a, b):
  n, m = len(a), len(b)
  if not n or not m: return []
  if min(n, m) <= 60:
    if n < m:
      n, m = m, n
      a, b = b, a
    ans = [0] * (n + m - 1)
    for i in range(n):
      for j in range(m):
        ans[i + j] += a[i] * b[j]
    return ans
  z = 1 << ceil_pow2(n + m - 1)
  a = a + [ModInt(0)] * (z - len(a))
  a = butterfly(a)
  b = b + [ModInt(0)] * (z - len(b))
  b = butterfly(b)
  for i in range(z): a[i] *= b[i]
  a = butterfly_inv(a)
  iz = ModInt(z).inv()
  for i in range(n + m - 1): a[i] *= iz
  return a[:n + m - 1]

def butterfly(a):
  MOD = ModInt.MOD
  g = sympy.primitive_root(MOD)
  n = len(a)
  h = ceil_pow2(n)

  first = True
  sum_e = [ModInt(0)] * 30
  if first:
    es, ies = [ModInt(0)] * 30, [ModInt(0)] * 30
    cnt2 = bsf(MOD - 1)
    e = ModInt(g) ** ((MOD - 1) >> cnt2) 
    ie = e.inv()
    for i in range(cnt2, 1, -1):
      es[i - 2] = e
      ies[i - 2] = ie
      e *= e
      ie *= ie
    now = ModInt(1)
    for i in range(cnt2 - 2):
      sum_e[i] = es[i] * now
      now *= ies[i]
  for ph in range(1, h + 1):
    w, p = 1 << (ph - 1), 1 << (h - ph)
    now = ModInt(1)
    for s in range(w):
      offset = s << (h - ph + 1)
      for i in range(p):
        l = ModInt(a[i + offset])
        r = ModInt(a[i + offset + p] * now)
        a[i + offset] = l + r
        a[i + offset + p] = l - r
      now *= sum_e[bsf(~s)]
  return a

def butterfly_inv(a):
  MOD = ModInt.MOD
  g = sympy.primitive_root(MOD)
  n = len(a)
  h = ceil_pow2(n)

  first = True
  sum_ie = [ModInt(0)] * 30
  if first:
    first = False
    es, ies = [ModInt(0)] * 30, [ModInt(0)] * 30
    cnt2 = bsf(MOD - 1)
    e = ModInt(g) ** ((MOD - 1) >> cnt2)
    ie = e.inv()
    for i in range(cnt2, 1, -1):
      es[i - 2] = e
      ies[i - 2] = ie
      e *= e
      ie *= ie
    now = ModInt(1)
    for i in range(cnt2 - 2):
      sum_ie[i] = ies[i] * now
      now *= es[i]
  for ph in range(h, 0, -1):
    w, p = 1 << (ph - 1), 1 << (h - ph)
    inow = ModInt(1)
    for s in range(w):
      offset = s << (h - ph + 1)
      for i in range(p):
        l = ModInt(a[i + offset])
        r = ModInt(a[i + offset + p])
        a[i + offset] = l + r
        a[i + offset + p] = MOD + l.val() - r.val() * inow.val()
      inow *= sum_ie[bsf(~s)]
  return a

def ceil_pow2(n):
  x = 0
  while (1 << x) < n: x += 1
  return x

def bsf(n):
  if n == 0: return 64
  x = n.val() if isinstance(n, ModInt) else n
  y = x & -x
  i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
  return _BIT_TABLE[i]

class ModInt:
  MOD = 10 ** 9 + 7
  def __init__(s, x):
    if type(x) == int:
      s.x = x % type(s).MOD
    else:
      s.x = x
 
  @classmethod
  def set_mod(c, m):
    c.MOD = m
 
  def inv(s):
    return type(s)(pow(s.x, type(s).MOD - 2, type(s).MOD))

  def val(s):
    return s.x
 
  def __str__(s):
    return str(s.x)
 
  __repr__ = __str__
 
  def __add__(s, t):
    return type(s)(s.x + t.x) if isinstance(t, ModInt) else type(s)(s.x + t)
 
  def __sub__(s, t):
    return type(s)(s.x - t.x) if isinstance(t, ModInt) else type(s)(s.x - t)
 
  def __mul__(s, t):
    return type(s)(s.x * t.x) if isinstance(t, ModInt) else type(s)(s.x * t)
 
  def __truediv__(s, t):
    return type(s)(s.x * pow(t.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(s.x * pow(t, type(s).MOD - 2, type(s).MOD))
 
  def __pow__(s, t):
    return type(s)(pow(s.x, t.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(s.x, t, type(s).MOD))
 
  __radd__ = __add__
 
  def __rsub__(s, t):
    return type(s)(t.x - s.x) if isinstance(t, ModInt) else type(s)(t - s.x)
 
  __rmul__ = __mul__
 
  def __rtruediv__(s, t):
    return type(s)(t.x * pow(s.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(t * pow(s.x, type(s).MOD - 2, type(s).MOD))
 
  def __rpow__(s, t):
    return type(s)(pow(t.x, s.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(t, s.x, type(s).MOD))
 
  def __eq__(s, t):
    return s.x == t.x if isinstance(t, ModInt) else s.x == t
 
  def __lt__(s, t):
    return s.x < t.x if isinstance(t, ModInt) else s.x < t
 
  def __le__(s, t):
    return s.x <= t.x if isinstance(t, ModInt) else s.x <= t
 
  def __gt__(s, t):
    return s.x > t.x if isinstance(t, ModInt) else s.x > t
 
  def __ge__(s, t):
    return s.x >= t.x if isinstance(t, ModInt) else s.x >= t

N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 998244353
ans = convolution(a, b, MOD)
print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
# 動作テスト
# ACならAtCoder LibraryのPython版Convolution翻訳完了

class convolution:
    def __init__(self, a: list, b: list, mod: int):
        self.a, self.b = a, b
        self.n, self.m = len(a), len(b)
        self.MOD = mod
        self.g = self.__primitive_root_constexpr()
    
    def convolution(self) -> list:
        n, m = self.n, self.m
        a, b = self.a, self.b
        if not n or not m: return []
        if min(n, m) <= 60:
            if n < m:
                n, m = m, n
                a, b = b, a
            ans = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    ans[i + j] += a[i] * b[j] % self.MOD
                    ans[i + j] %= self.MOD
            return ans
        z = 1 << self.ceil_pow2(n + m - 1)
        a = self.resize(a, z)
        a = self.butterfly(a)
        b = self.resize(b, z)
        b = self.butterfly(b)
        for i in range(z): a[i] = a[i] * b[i] % self.MOD
        a = self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = self.inv(z)
        a = [x * iz % self.MOD for x in a]
        return a

    def butterfly(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)
        first = True
        sum_e = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_e[i] = es[i] * now % m
                now = now * ies[i] % m
        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[i + offset] % m
                    r = a[i + offset + p] * now % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (l - r) % m
                now = now * sum_e[bsf(~s)] % m
        return a

    def butterfly_inv(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)        
        first = True
        sum_ie = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_ie[i] = ies[i] * now % m
                now = es[i] * now % m
        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[i + offset] % m
                    r = a[i + offset + p] % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (m + l - r) * inow % m
                inow = sum_ie[bsf(~s)] * inow % m
        return a

    @staticmethod
    def resize(array: list, sz: int) -> list:
        new_array = array + [0] * (sz - len(array))
        return new_array
    @staticmethod
    def ceil_pow2(n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x
    @staticmethod
    def bsf(n: int) -> int:
        return (n & -n).bit_length() - 1
    def inv(self, x: int):
        if self.__is_prime_constexpr():
            assert x
            return self.mypow(x, self.MOD - 2)
        else:
            eg = self.__inv_gcd(x)
            assert eg[0] == 1
            return eg[1]
    def mypow(self, x: int, n: int) -> int:
        assert 0 <= n
        r = 1
        while n:
            if n & 1: r = r * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return r
    # private
    def __is_prime_constexpr(self) -> bool:
        n = self.MOD
        if n <= 1: return False
        if n == 2 or n == 7 or n == 61: return True
        if n % 2 == 0: return False
        d = n - 1
        while d % 2 == 0: d //= 2
        for a in [2, 7, 61]:
            t = d
            y = self.__pow_mod_constexpr(a, t, n)
            while t != n - 1 and y != 1 and y != n - 1:
                y = y * y % n
                t <<= 1
            if y != n - 1 and t % 2 == 0: return False
        return True
    def __pow_mod_constexpr(self, x: int, n: int, m: int) -> int:
        if m == 1: return 0
        _m = m; r = 1; y = self.__safe_mod(x, m)
        while n:
            if n & 1: r = (r * y) % _m
            y = (y * y) % _m
            n >>= 1
        return r
    def __safe_mod(self, x: int, m: int) -> int:
        x %= m
        if x < 0: x += m
        return x
    def __inv_gcd(self, a: int) -> tuple:
        b = self.MOD; a = safe_mod(a, b)
        if a == 0: return (b, 0)
        s = b; t = a; m0 = 0; m1 = 1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp
        if m0 < 0: m0 += b // s
        return (s, m0)
    def __primitive_root_constexpr(self) -> int:
        m = self.MOD
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [0] * 20
        divs[0] = 2
        cnt = 1
        x = (m - 1) // 2
        while x % 2 == 0: x //= 2
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs[cnt] = i; cnt += 1
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1: divs[cnt] = x; cnt += 1
        g = 2
        while True:
            ok = True
            for i in range(cnt):
                if self.__pow_mod_constexpr(g, (m - 1) // divs[i], m) == 1:
                    ok = False
                    break
            if ok: return g
            g += 1

#----------convolution class end----------

# Date [ 2020-09-11 15:37:28 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    a = read_int_list()
    b = read_int_list()
    a = [x % MOD for x in a]
    b = [x % MOD for x in b]
    cnv = convolution(a, b, MOD)
    ans = cnv.convolution()
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Runtime Error

Solution code:
import numpy as np

n,m=map(int,input().split())
mod=998244353
f = np.array([0]*(2**19))
g = np.array([0]*(2**19))
f[0:n]=list(map(int,input().split()))
g[0:m]=list(map(int,input().split()))
fft_len = 20  # |f|+|g|-1 以上の2の冪数
 
# f,gをフーリエ変換
Ff = np.fft.rfft(f, fft_len)
#print(Ff)
Fg = np.fft.rfft(g, fft_len)
#print(Fg)
 
# 各要素について掛け合わせる
Ffg = Ff * Fg
#print(Ffg)
 
# 逆変換後、整数に丸める
fg = np.fft.irfft(Ffg, fft_len)
fg = np.rint(fg)
for i in range(n+m-1):
  print(int(fg[i])%mod,end=" ")