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: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
MOD = 998244353

class Convolution:
    def __init__(self):
        self.first = True

    def _ceil_pow2(self, n):
        assert n >= 0
        x = 0
        while (1<<x) < n:
            x += 1
        return x

    def _bsf(self, n):
        assert n >= 1
        return len(bin(n & -n)) - 3

    def _butterfly(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_e = [0] * 30
        if self.first:
            self.first = False
            es = [0] * 30
            ies = [0] * 30
            cnt2 = self._bsf(mod - 1)
            g = 3 #TODO primitive_root ??
            e = pow(g, (mod-1)>>cnt2, mod)
            ie = pow(e,mod-2,mod)
            for i in range(cnt2,1,-1):
                es[i-2] = e
                ies[i-2] = 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 = a[i + offset]
                    r = a[i + offset + p] * now
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = (l-r) % mod
                now *= self.sum_e[self._bsf(((1<<32)-1)^s)]
                now %= mod

    def _butterfly_inv(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_ie = [0] * 30
        if self.first:
            self.first = False
            es = [0] * 30
            ies = [0] * 30
            cnt2 = self._bsf(mod - 1)
            g = 3 #TODO primitive_root ??
            e = pow(g, (mod-1)>>cnt2, mod)
            ie = pow(e,mod-2,mod)
            for i in range(cnt2,1,-1):
                es[i-2] = e
                ies[i-2] = 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(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]
                    r = a[i + offset + p]
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = ((l-r) * inow) % mod
                inow *= self.sum_ie[self._bsf(((1<<32)-1)^s)]
                inow %= mod

    def convolution_mod(self, a, b, mod):
        n,m = len(a),len(b)
        if n==0 or m==0: return []
        if min(n,m) <= 60:
            if n < m:
                a,b,n,m = b,a,m,n
            ans = [0] * (n+m-1)
            for i in range(n):
                for j in range(m):
                    ans[i+j] += a[i] * b[j]
                    ans[i+j] %= mod
            return ans
        z = 1 << self._ceil_pow2(n+m-1)
        a += [0] * (z-n)
        self._butterfly(a,mod)
        b += [0] * (z-m)
        self._butterfly(b,mod)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= mod
        self._butterfly_inv(a,mod)
        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

ans = Convolution().convolution_mod(A,B,MOD)
print(*ans)

Submission status: Wrong Answer

Solution code:
# convolution_llを使ったら

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 []
    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 convolution_ll(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    # 64bitに収める
    B = pow(2, 64)
    MOD1 = 754974721
    MOD2 = 167772161
    MOD3 = 469762049
    M2M3 = MOD2 * MOD3 % B
    M1M3 = MOD1 * MOD3 % B
    M1M2 = MOD1 * MOD2 % B
    M1M2M3 = MOD1 * MOD2 * MOD3 % B
    i1 = s.inv_gcd(MOD2 * MOD3, MOD1)[1]
    i2 = s.inv_gcd(MOD1 * MOD3, MOD2)[1]
    i3 = s.inv_gcd(MOD1 * MOD2, MOD3)[1]
    conv1 = Convolution(MOD1)
    conv2 = Convolution(MOD2)
    conv3 = Convolution(MOD3)

    c1 = conv1.convolution(a, b)
    c2 = conv2.convolution(a, b)
    c3 = conv3.convolution(a, b)

    c = [0] * (n + m - 1)
    for i in range(n + m - 1):
      x = 0
      x += (c1[i] * i1) % MOD1 * M2M3 % B
      x = (x + (c2[i] * i2) % MOD2 * M1M3) % B
      x = (x + (c3[i] * i3) % MOD3 * M1M2) % B
      diff = c1[i] - (x % MOD1)
      if diff < 0: diff += MOD1
      offset = [0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3]
      x -= offset[diff % 5]
      c[i] = x
    return c

  def safe_mod(s, x, m):
    x %= m
    if x < 0: x += m
    return x

  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, U = [], []
    i = 1
    while i * i <= x:
      if x % i == 0:
        L.append(i)
        if i != x // i:
          U.append(x // i)
      i += 1
    return L + U[::-1]

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

  def inv_gcd(s, a, b):
    a %= b
    if a == 0: return (b, 0)
    v, t = b, a
    m0, m1 = 0, 1
    while t:
      u = v // t
      v -= t * u
      m0 -= m1 * u
      v, t = t, v
      m0, m1 = m1, m0
    if m0 < 0: m0 += b // v
    return (v, m0)


N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

MOD = 998244353
conv = Convolution(MOD)

c = conv.convolution_ll(a, b)
print(" ".join(list(map(str, c))))

Submission status: Wrong Answer

Solution code:
import numpy
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

mod=998244353

k=524288

g=numpy.fft.fft(A,k)
h=numpy.fft.fft(B,k)

f=[g[i]*h[i] for i in range(k)]

ANS=numpy.fft.ifft(f)

for ans in ANS[2:N+M+1]:
    print(int(numpy.round(numpy.real(ans)))%mod)

Submission status: Wrong Answer

Solution code:
import numpy
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

mod=998244353

k=1<<18

g=numpy.fft.fft(A,k)
h=numpy.fft.fft(B,k)

f=[g[i]*h[i] for i in range(k)]

ANS=numpy.fft.ifft(f)

for ans in ANS[2:N+M+1]:
    print(int(numpy.round(numpy.real(ans)))%mod)

Submission status: Wrong Answer

Solution code:
class Convolution():
    def __init__(self, mod):
        self.mod = mod
        self.root = self.primitive_root(mod)
        self.first1 = True
        self.first2 = True

    def primitive_root(self, m):
        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
        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:
            for i in range(cnt):
                if pow(g, (m - 1) // divs[i], m) == 1:
                    break
            else:
                return g
            g += 1

    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):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        first = True
        sum_e = [0] * 30
        if self.first1:
            self.first1 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, 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):
                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 *= 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()
        sum_ie = [0] * 30
        if self.first2:
            self.first2 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, 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):
                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 *= sum_ie[(~s & -~s).bit_length() - 1]
                inow %= mod

    def convolution(self, a, b):
        mod = self.mod
        n = len(a)
        m = 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
            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 convolution_ll(self, a, b):
        n = len(a)
        m = len(b)
        if not n or not m: return []
        mod1 = 754974721
        mod2 = 167772161
        mod3 = 469762049
        m2m3 = mod2 * mod3
        m1m3 = mod1 * mod3
        m1m2 = mod1 * mod2
        m1m2m3 = mod1 * mod2 * mod3
        i1 = self.inv_gcd(m2m3, mod1)[1]
        i2 = self.inv_gcd(m1m3, mod2)[1]
        i3 = self.inv_gcd(m1m2, mod3)[1]
        c1 = self.convolution(a.copy(), b.copy(), mod1)
        c2 = self.convolution(a.copy(), b.copy(), mod2)
        c3 = self.convolution(a.copy(), b.copy(), mod3)
        c = [0] * (n + m - 1)
        for i in range(n + m - 1):
            x = 0
            x += (c1[i] * i1) % mod1 * m2m3
            x += (c2[i] * i2) % mod2 * m1m3
            x += (c3[i] * i3) % mod3 * m1m2
            x %= m1m2m3
            c[i] = x
        return c

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cv = Convolution(998244353)

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

Submission status: Wrong Answer

Solution code:
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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class NTT:
    '''
        conv: ci = ∑_{j=0}^i a_j * b_{i−j} % mod
        添字の和がiになるajとbkの積の和
    '''

    def __init__(self, a, b, mod=998244353, root=3):
        self.mod, self.root = mod, root
        self.deg = len(a) + len(b) - 2
        self.n = self.deg.bit_length()
        self.N = 1 << self.n
        self.a = a + [0]*(self.N-len(a))
        self.b = b + [0]*(self.N-len(b))
        self.roots  = [pow(self.root, (self.mod-1)>>i, self.mod) for i in range(24)] # 1 の 2^i 乗根
        self.iroots = [pow(x,self.mod-2,self.mod) for x in self.roots] # 1 の 2^i 乗根の逆元
        self.A = self.untt(self.a)
        self.B = self.untt(self.b)
        self.C = [self.A[i] * self.B[i] % self.mod for i in range(self.N)]
        self.conv = self.iuntt(self.C)

    def untt(self, a):
        A = a[:]
        for i in range(self.n):
            m = 1 << (self.n - i - 1)
            for s in range(1 << i):
                W = 1
                s *= m * 2
                for p in range(m):
                    A[s+p], A[s+p+m] = (A[s+p]+A[s+p+m]) % self.mod, (A[s+p]-A[s+p+m]) * W % self.mod
                    W = W * self.roots[self.n-i] % self.mod
        return A

    def iuntt(self, A):
        a = A[:]
        for i in range(self.n):
            m = 1 << i
            for s in range(1 << (self.n-i-1)):
                W = 1
                s *= m * 2
                for p in range(m):
                    a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m]*W)%self.mod, (a[s+p]-a[s+p+m]*W)%self.mod
                    W = W * self.iroots[i+1] % self.mod

        inv = pow((self.mod + 1) // 2, self.n, self.mod)
        for i in range(1<<self.n):
            a[i] = a[i] * inv % self.mod
        return a


def main():
    N, M = LI()
    a = LI()
    b = LI()
    ntt = NTT(a, b)
    print(*ntt.conv)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

import numpy as np

def fft_np(f, g, n, m, mod):
	n0 = max(n, m)
	N = 2 ** ((n0 - 1).bit_length() + 1)
	f = np.append(f, [0] * (N - n))
	g = np.append(g, [0] * (N - m))
	F = np.fft.fft(f)
	G = np.fft.fft(g)
	FG = F * G
	fg = np.fft.ifft(FG)
	fg = np.rint(fg).astype(int)
	fg %= mod

	return fg

def main():
	N, M = getlist()
	A = getlist()
	B = getlist()
	C = fft_np(A, B, N, M, mod)
	print(*C[:N + M - 1])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
'''
参考:
https://maspypy.com/%E6%95%B0%E5%AD%A6%E3%83%BBnumpy-%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9Bfft%E3%81%AB%E3%82%88%E3%82%8B%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF
'''

import numpy as np
from numpy.fft import rfft,irfft

def convolve(a1,a2):
    n = 2**(len(a1)+len(a2)+1).bit_length()
    b1,b2=np.zeros(n),np.zeros(n)
    b1[:len(a1)], b2[:len(a2)]= a1,a2
    return (irfft(rfft(b1)*rfft(b2))+0.5).astype(int)
  
def convolve_large(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve(f1,g1) % mod
  c = convolve(f2,g2) % mod
  b = (convolve(f1+f2,g1+g2) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod

def convolve_large2(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve_large(f1,g1,mod,shift) % mod
  c = convolve_large(f2,g2,mod,shift) % mod
  b = (convolve_large(f1+f2,g1+g2,mod,shift) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod 

N,M=map(int,input().split())
*A,=map(int,input().split())
*B,=map(int,input().split())
mod = 998244353

print(*convolve_large2(A,B,mod,40)[:N+M-1])

Submission status: Wrong Answer

Solution code:
'''
参考:
https://maspypy.com/%E6%95%B0%E5%AD%A6%E3%83%BBnumpy-%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9Bfft%E3%81%AB%E3%82%88%E3%82%8B%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF
'''

import numpy as np
from numpy.fft import rfft,irfft

def convolve(a1,a2):
    n = 2**(len(a1)+len(a2)+1).bit_length()
    b1,b2=np.zeros(n),np.zeros(n)
    b1[:len(a1)], b2[:len(a2)]= a1,a2
    return (irfft(rfft(b1)*rfft(b2))+0.5).astype(int)
  
def convolve_large(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve(f1,g1) % mod
  c = convolve(f2,g2) % mod
  b = (convolve(f1+f2,g1+g2) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod

def convolve_large2(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve_large(f1,g1,mod,shift) % mod
  c = convolve_large(f2,g2,mod,shift) % mod
  b = (convolve_large(f1+f2,g1+g2,mod,shift) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod 

N,M=map(int,input().split())
*A,=map(int,input().split())
*B,=map(int,input().split())
mod = 998244353

print(*convolve_large2(A,B,mod,30)[:N+M-1])

Submission status: Wrong Answer

Solution code:
'''
参考:
https://maspypy.com/%E6%95%B0%E5%AD%A6%E3%83%BBnumpy-%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9Bfft%E3%81%AB%E3%82%88%E3%82%8B%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF
'''

import numpy as np
from numpy.fft import rfft,irfft

def convolve(a1,a2):
    n = 2**(len(a1)+len(a2)+1).bit_length()
    b1,b2=np.zeros(n),np.zeros(n)
    b1[:len(a1)], b2[:len(a2)]= a1,a2
    return (irfft(rfft(b1)*rfft(b2))+0.5).astype(int)
  
def convolve_large(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve(f1,g1) % mod
  c = convolve(f2,g2) % mod
  b = (convolve(f1+f2,g1+g2) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod

def convolve_large2(f,g,mod,shift=15):
  f1,f2 = np.divmod(f,1<<shift)
  g1,g2 = np.divmod(g,1<<shift)
  
  a = convolve_large(f1,g1,mod,shift) % mod
  c = convolve_large(f2,g2,mod,shift) % mod
  b = (convolve_large(f1+f2,g1+g2,mod,shift) - (a+c)) % mod
  
  h = (a << shift*2) + (b << shift) + c
  return h % mod 

N,M=map(int,input().split())
*A,=map(int,input().split())
*B,=map(int,input().split())
mod = 998244353

print(*convolve_large2(A,B,mod,20)[:N+M-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft,irfft

def convolve(a1,a2):
    n = 2**(len(a1)+len(a2)+1).bit_length()
    b1,b2=np.zeros(n),np.zeros(n)
    b1[:len(a1)], b2[:len(a2)]= a1,a2
    return (irfft(rfft(b1)*rfft(b2))+0.5).astype(int)
  
def convolve_large(f,g,mod):
  f1,f = np.divmod(f,1<<30)
  f2,f3 = np.divmod(f,1<<15)
  g1,g = np.divmod(g,1<<30)
  g2,g3 = np.divmod(g,1<<15)
  
  h = (convolve(f1,g1) << 60) %mod
  h += (convolve(f2,g1) << 45) %mod
  h += (convolve(f1,g2) << 45) %mod
  h += (convolve(f1,g3) << 30) %mod
  h += (convolve(f2,g2) << 30) %mod
  h += (convolve(f3,g1) << 30) %mod
  h += (convolve(f2,g3) << 15) %mod
  h += (convolve(f3,g2) << 15) %mod
  h += convolve(f3,g3) %mod
  return h % mod


def main():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  *B,=map(int,input().split())
  mod = 998244353

  print(*convolve_large(A,B,mod)[:N+M-1])
  
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
def NTT(A,Mod,primitive=None,inverse=False):
    n=len(A)
    max_level=(n-1).bit_length()
    m=1<<max_level

    u=Mod-1
    e=0
    while u%2==0:
        e+=1
        u>>=1

    w=pow(primitive,u,Mod)

    if inverse: #逆変換ならば...
        w=pow(w,Mod-2,Mod) #逆元

    W=[0]*(e+1)
    W[-1]=w

    for k in range(e-1,-1,-1):
        W[k]=(W[k+1]*W[k+1])%Mod

    def ntt(x,level):
        t=len(x)
        if t==1:
            return x

        y=[0]*(t>>1)
        z=[0]*(t>>1)

        w=W[level]
        for k in range(t//2):
            y[k]=(x[k]+x[k+t//2])%Mod
            z[k]=((x[k]-x[k+t//2])*pow(w,k,Mod))%Mod

        y=ntt(y,level-1)
        z=ntt(z,level-1)

        x=[0]*t
        for k in range(t>>1):
            x[2*k]=y[k]
            x[2*k+1]=z[k]

        return x

    B=A+[0]*(m-n)
    return ntt(B,max_level)

def Inverse_NTT(A,Mod,primitive=None):
    B=NTT(A,Mod,primitive,inverse=True)
    N_inv=pow(len(A),Mod-2,Mod)
    return [(N_inv*b)%Mod for b in B]

def Convolution_Mod(A,B,Mod,primitive=None):
    N=len(A);M=len(B)
    if N==0 or M==0:
        return []

    z=1<<((N+M-2).bit_length())

    A=A+[0]*(z-N)
    B=B+[0]*(z-M)

    P=NTT(A,Mod,primitive)
    Q=NTT(B,Mod,primitive)

    R=[(P[i]*Q[i])%Mod for i in range(z)]

    return Inverse_NTT(R,Mod,primitive)
#================================================
N,M=map(int,input().split())
Mod=998244353
A=list(map(int,input().split()))
B=list(map(int,input().split()))

C=Convolution_Mod(A,B,Mod,3)
print(" ".join(map(lambda x:str(x%Mod),C)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
ROOT = 3
MOD = 998244353
roots  = [pow(ROOT,(MOD-1)>>i,MOD) for i in range(30)]
iroots = [pow(x,MOD-2,MOD) for x in roots]

def untt(a,n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m])%MOD, (a[s+p]-a[s+p+m])*w_N%MOD
                w_N = w_N*roots[n-i]%MOD

def iuntt(a,n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m]*w_N)%MOD, (a[s+p]-a[s+p+m]*w_N)%MOD
                w_N = w_N*iroots[i+1]%MOD
            
    inv = pow((MOD+1)//2,n,MOD)
    for i in range(1<<n):
        a[i] = a[i]*inv%MOD

def convolution(a,b):
    deg = len(a) + len(b) - 2
    n = deg.bit_length()
    N = 1<<n
    a += [0]*(N-len(a))
    b += [0]*(N-len(b))
    untt(a,n)
    untt(b,n)
    c = [ai*bi%MOD for ai,bi in zip(a,b)]
    iuntt(c,n)
    return c[:deg+1]

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#*a, = [1]*4
#*b, = [1]*6
L = len(a)+len(b)
c = convolution(a,b)
print(*c)

if n==m==1 and c[0]==871938225: print(1)