Problem p02563 (python)

Fixed submission:
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] = (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))))

Buggy submission (verdict: Runtime Error):
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))))

Buggy submission (verdict: Runtime Error):
import numpy as np
from numpy.fft import fft
from numpy.fft import ifft

_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)
  Primitive_Root = primitive_root(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, Primitive_Root)
  c = [0] * (n + m - 1)
  for i in range(n + m - 1):
    c[i] = c2[i].val()
  return c

def convolutionModInt(a, b, Primitive_Root):
  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 - n)
  a = butterfly(a, Primitive_Root)
  b = b + [ModInt(0)] * (z - m)
  b = butterfly(b, Primitive_Root)
  for i in range(z): a[i] *= b[i]
  a = butterfly_inv(a, Primitive_Root)
  iz = ModInt(z).inv()
  for i in range(n + m - 1): a[i] *= iz
  return a[:n + m - 1]

def butterfly(a, Primitive_Root):
  MOD = ModInt.MOD
  g = Primitive_Root
  n = len(a)
  h = ceil_pow2(n)

  first = True
  sum_e = [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_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, Primitive_Root):
  MOD = ModInt.MOD
  g = Primitive_Root
  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]

def prime(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(x):
  L = 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

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))))

Buggy submission (verdict: Runtime Error):
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))))