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: Time Limit Exceeded

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# とりあえずpythonに変換したけどバグだらけｗ
# 今の自分の力量ではここら辺が限界かも...後は上級者の翻訳待ち

# convolution.py
def butterfly(a: list):
    n = len(a)
    h = ceil_pow2(n)
    g = primitive_root(Mint().mod())
    
    first = True
    sum_e = [0] * 30
    if first:
        first = False
        es = [0] * 30; ies = [0] * 30
        cnt2 = bsf(Mint().mod() - 1)
        e = Mint(Mint(g).pow_((Mint().mod() - 1) >> cnt2)); ie = Mint(e.inv())
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e *= e
            ie *= ie
        now = Mint(1)
        for i in range(cnt2 - 2):
            sum_e[i] = es[i] * now
            now *= ies[i]
    for ph in range(1, h + 1):
        w = 1 << (ph - 1); p = 1 << (h - ph)
        now = Mint(1)
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = Mint(a[i + offset])
                r = Mint(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: list):
    n = len(a)
    h = ceil_pow2(n)
    g = primitive_root(Mint().mod())
    
    first = True
    sum_ie = [0] * 30
    if first:
        first = False
        es = [0] * 30; ies = [0] * 30
        cnt2 = bsf(Mint().mod() - 1)
        e = Mint(Mint(g).pow_((Mint().mod() - 1) >> cnt2)); ie = Mint(e.inv())
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e *= e
            ie *= ie
        now = Mint(1)
        for i in range(cnt2 - 2):
            sum_ie[i] = es[i] * now
            now *= ies[i]
    for ph in range(h, 0, -1):
        w = 1 << (ph - 1); p = 1 << (h - ph)
        inow = Mint(1)
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = Mint(a[i + offset])
                r = Mint(a[i + offset + p])
                a[i + offset] = l + r
                a[i + offset + p] = (Mint().mod() + l.val() - r.val()) * inow.val()
            inow *= sum_ie[bsf(~s)]
    return a
    
def convolution(a: list, b: list):
    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
        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 + [0] * (z - len(a))
    a = butterfly(a)
    b = b + [0] * (z - len(a))
    b = butterfly(b)
    for i in range(z):
        a[i] *= b[i]
    a = butterfly_inv(a)
    a = a[:n + m - 2]
    iz = Mint(Mint(z).inv())
    for i in range(n + m - 1): a[i] *= iz
    return a

def convolution_sub(a: list, b: list):
    n = len(a); m = len(b)
    if not n or not m: return []
    # using mint = static_modint<mod> ??
    a2 = [Mint(a[i]) for i in range(n)]
    b2 = [Mint(b[i]) for i in range(m)]

    c2 = convolution(a2, b2)
    c = [c2[i].val() for i in range(n + m - 1)]
    return c

# internal_math.py
def safe_mod(x: int, m: int) -> int:
    x %= m
    if x < 0: x += m
    return x

class barrett:
    def __init__(self, m: int):
        self._m = m
        self.im = -1 // (m + 1)
    def umod(self): return self._m
    def mul(self, a: int, b: int) -> int:
        z = a
        z *= b
        x = (z * im) >> 64
        v = z - x * self._m
        if self._m <= v: v += self._m
        return v        

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
    if m == 1: return 0
    _m = m; r = 1; y = safe_mod(x, m)
    while n:
        if n & 1: r = (r * y) % _m
        y = (y * y) % _m
        n >>= 1
    return r

def is_prime_constexpr(n: int) -> bool:
    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 = 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 is_prime(n: int) -> bool: return is_prime_constexpr(n)

def inv_gcd(self, a: int, b: int) -> tuple:
    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(m: int) -> int:
    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 pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
                ok = False
                break
        if ok: return g
        g += 1

def primitive_root(m: int) -> int: return primitive_root_constexpr(m)

# modint.py
class Mint:
    modint1000000007 = 1000000007
    modint998244353 = 998244353

    def __init__(self, v: int = 0):
        # self.m = self.modint1000000007
        self.m = self.modint998244353
        self.x = v % self.__umod()
    
    def inv(self):
        if self.__is_prime_constexpr(self.__umod()):
            assert self.x
            return self.pow_(self.__umod() - 2)
        else:
            eg = self.__inv_gcd(self.x, self.m)
            assert eg[0] == 1
            return eg[2]

    def __str__(self): return str(self.x)
    def __le__(self, other): return self.x <= Mint.__get_val(other)
    def __lt__(self, other): return self.x < Mint.__get_val(other)
    def __ge__(self, other): return self.x >= Mint.__get_val(other)
    def __gt(self, other): return self.x > Mint.__get_val(other)
    def __eq__(self, other): return self.x == Mint.__get_val(other)
    
    def __iadd__(self, other):
        self.x += Mint.__get_val(other)
        if self.x >= self.__umod(): self.x -= self.__umod()
        return self
    def __add__(self, other):
        _v = Mint(self.x); _v += other
        return _v

    def __isub__(self, other):
        self.x -= Mint.__get_val(other)
        if self.x >= self.__umod(): self.x += self.__umod()
        return self
    def __sub__(self, other):
        _v = Mint(self.x); _v -= other
        return _v
    def __rsub__(self, other):
        _v = Mint(Mint.__get_val(other)); _v -= self
        return _v
    
    def __imul__(self, other):
        self.x =self.x * Mint.__get_val(other) % self.__umod()
        return self
    def __mul__(self, other):
        _v = Mint(self.x); _v *= other
        return _v

    def __itruediv__(self, other):
        self.x = self.x / Mint.__get_val(other) % self.__umod()
        return self
    def __truediv__(self, other):
        _v = Mint(self.x); _v /= other
        return _v
    def __rtruediv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v /= self
        return _v
    
    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inv()
        return self
    def __floordiv__(self, other):
        _v = Mint(self.x); _v //= other
        return _v
    def __rfloordiv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v //= self
        return _v

    def __pow__(self, other):
        _v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
        return _v
    def __rpow__(self, other):
        _v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
        return _v

    def __imod__(self, other):
        self.x %= Mint.__get_val(other)
        return self
    def __mod__(self, other):
        _v = Mint(self.x); _v %= other
        return _v
    def __rmod__(self, other):
        _v = Mint(Mint.__get_val(other)); _v %= self
        return _v

    def __ilshift__(self, other):
        self.x <<= Mint.__get_val(other)
        return self
    def __irshift__(self, other):
        self.x >>= Mint.__get_val(other)
        return self
    def __lshift__(self, other):
        _v = Mint(self.x); _v <<= other
        return _v
    def __rshift__(self, other):
        _v = Mint(self.x); _v >>= other
        return _v
    def __rlshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v <<= self
        return _v
    def __rrshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v >>= self
        return _v
    
    __repr__ = __str__
    __radd__ = __add__
    __rmul__ = __mul__

    def __umod(self): return self.m
    
    @staticmethod
    def __get_val(val): return val.x if isinstance(val, Mint) else val

    def __inv_gcd(self, a: int, b: int) -> tuple:
        a = self.__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)

    @staticmethod
    def __safe_mod(x: int, m: int) -> int:
        x %= m
        if x < 0: x += m
        return x

    def __is_prime_constexpr(self, n: int) -> bool:
        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 pow_(self, n: int):
        print(n)
        assert 0 <= n
        x = Mint(self.x); r = 1
        while n:
            if n & 1: r *= x
            x *= x
            n >>= 1
        return r
    def val(self): return self.x
    def mod(self): return self.m
    def raw(self, v):
        x = Mint()
        x.x = v
        return x

# internal_bit.py
def ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n: x += 1
    return x

def bsf(n: int) -> int:
    return (n & -n).bit_length() - 1

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 = 10 ** 9 + 7
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()
    ans = convolution_sub(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
ctypedef long long LL
# cython: cdivision=True
from libc.stdio cimport scanf
from libcpp.vector cimport vector
ctypedef vector[LL] vec
ctypedef vector[vec] vec_vec

cdef LL mod,omege,rev_omega

mod = 998244353
omega = pow(3,119,mod)
rev_omega = pow(omega,mod-2,mod)

cdef vec _ntt(vec f,LL L,reverse=False):
    cdef vec F,res
    cdef LL n,i,j,a,base,size,wj,use_omega,w

    F = f
    n = L.bit_length() - 1
    base = omega
    if reverse:
        base = rev_omega

    if not n:
        return F

    size = 2**n
    wj = pow(base,2**22,mod)
    res = vec(2**n,0)

    for i in range(n,0,-1):
        use_omega = pow(base,2**(22+i-n),mod)
        res = vec(2**n,0)
        size //= 2
        w = 1
        for j in range(0,L//2,size):
            for a in range(size):
                res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod
                t = (w * wj) % mod
                res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod
            w = (w * use_omega) % mod
        F = res

    return res

cdef vec ntt(vec f,LL L=0):
    cdef LL l
    cdef vec F
    l = f.size()
    if not L:
        L = 1<<((l-1).bit_length())
    while f.size()<L:
        f.push_back(0)
    while f.size()>L:
        f.pop_back()
    F = _ntt(f,L)
    return F

cdef vec intt(vec f,LL L=0):
    cdef LL l,inv,i
    cdef vec F
    l = f.size()
    if not L:
        L = 1<<((l-1).bit_length())
    while f.size()<L:
        f.push_back(0)
    while f.size()>L:
        f.pop_back()
    F = _ntt(f,L,reverse=True)
    inv = pow(L,mod-2,mod)
    for i in range(L):
        F[i] *= inv
        F[i] %= mod
    return F

cdef vec convolve(vec f,vec g,limit):
    cdef LL l,L,i
    cdef vec F,G,H,h

    l = f.size()+g.size()-1
    L = 1<<((l-1).bit_length())

    F = ntt(f,L)
    G = ntt(g,L)

    H = vec(L,0)
    for i in range(L):
        H[i] = (F[i]*G[i]) % mod

    h = intt(H,L)

    while h.size()>limit:
        h.pop_back()
    return h

cdef LL N,M
cdef vec a,b,c

scanf("%lld %lld",&N,&M)
a = vec(N,0)
b = vec(M,0)

cdef LL i

for i in range(N):
    scanf("%lld",&a[i])
for i in range(M):
    scanf("%lld",&b[i])

c = convolve(a,b,N+M-1)

c = list(c)
print(*c)


'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 998244353

class FastModuloTransformation:
  def __init__(self, n):
    self.n = n

    self.P = 998244353
    self.g = 3
    self.omega = pow(self.g, (self.P - 1) // n, self.P)
  def bitrev(self, a):
    n = self.n
    x = n.bit_length() - 1
    res = a[: ]
    for i in range(n):
      j = 0
      for k in range(x): j |= (i & (1 << k) > 0) << (x - k - 1)
      if i < j: res[i], res[j] = res[j], res[i]
    return res
  def fmt(self, a, base):
    if n == 1: return a
    P = self.P
    omega = base
    A = self.bitrev(a)
    half = pow(omega, n >> 1, P)
    i = n
    m = 1
    while i > 1:
      i >>= 1
      w = pow(omega, i, P)
      wk = 1
      for j in range(m):
        for x in range(j, len(a), 2 * m):
          l = A[x]
          r = wk * A[x + m] % P
          A[x] = (l + r) % P
          A[x + m] = (l + r * half) % P
        wk *= w
        wk %= P
      m <<= 1
    return A
  def ifmt(self, A):
    if self.n == 1: return A
    P = self.P
    nrev = pow(self.n, P - 2, P)
    return [(x * nrev) % P for x in self.fmt(A, pow(self.omega, P - 2, P))]

n = 1 << ((max(len(a), len(b))).bit_length()) + 1
fmt = FastModuloTransformation(n)
a = [0] * (n - N) + a
b = [0] * (n - M) + b
A = fmt.fmt(a, fmt.omega)
B = fmt.fmt(b, fmt.omega)
AB = [A[i] * B[i] % mod for i in range(n)]
ab = fmt.ifmt(AB)
print(*ab[-(N + M): -1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 998244353

class FastModuloTransformation:
  def __init__(self, n):
    self.n = n

    self.P = 998244353
    self.g = 3
    self.omega = pow(self.g, (self.P - 1) // n, self.P)
  def bitrev(self, a):
    n = self.n
    x = n.bit_length() - 1
    res = a[: ]
    for i in range(n):
      j = 0
      for k in range(x): j |= (i & (1 << k) > 0) << (x - k - 1)
      if i < j: res[i], res[j] = res[j], res[i]
    return res
  def fmt(self, a, base):
    if n == 1: return a
    P = self.P
    omega = base
    A = self.bitrev(a)
    half = pow(omega, n >> 1, P)
    i = n
    m = 1
    while i > 1:
      i >>= 1
      w = pow(omega, i, P)
      wk = 1
      for j in range(m):
        for x in range(j, len(a), 2 * m):
          l = A[x]
          r = wk * A[x + m] % P
          A[x] = (l + r) % P
          A[x + m] = (l + r * half) % P
        wk *= w
        wk %= P
      m <<= 1
    return A
  def ifmt(self, A):
    if self.n == 1: return A
    P = self.P
    a = self.bitrev(A)
    nrev = pow(self.n, P - 2, P)
    return [(x * nrev) % P for x in self.fmt(A, pow(self.omega, P - 2, P))]

n = 1 << ((max(len(a), len(b))).bit_length() + 1)
fmt = FastModuloTransformation(n)
a = [0] * (n - N) + a
b = [0] * (n - M) + b
A = fmt.fmt(a, fmt.omega)
B = fmt.fmt(b, fmt.omega)
AB = [A[i] * B[i] % mod for i in range(n)]
ab = fmt.ifmt(AB)
print(*ab[-(N + M): -1])

Submission status: Time Limit Exceeded

Solution code:
class NTT:
    def __init__(self, convolution_rank, binary_level):
        self.cr = convolution_rank
        self.bl = binary_level
        self.modulo_list = [1]*convolution_rank
        self.primal_root_list = [1]*convolution_rank
        self.bin_list = [1]*(binary_level+1)
        self.primal_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        self.inverse_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        for i in range(binary_level):
            self.bin_list[i+1] = self.bin_list[i] * 2
    
    def doubling(self, n, m, modulo=0):
        y = 1
        tmp = m
        bas = n
        while tmp:
            if tmp % 2:
                y *= bas
                if modulo:
                    y %= modulo
            bas *= bas
            if modulo:
                bas %= modulo
            tmp >>= 1
        return y
    
    def powlimit(self, n):
        y = 1
        cnt = 0
        while y < n:
            y *= 2
            cnt += 1
        return y, cnt
    
    def IsPrime(self, num):
        p = 2
        if num <= 1:
            return False
        while p * p <= num:
            if num % p == 0:
                return False
            p += 1
        return True
    
    def extgcd(self, a, b, c):
        x, y, u, v, k, l = 1, 0, 0, 1, a, b
        while l:
            x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
            k, l = l, k % l
        if c % k:
            return "No Solution"
        return x * c, y * c
    
    def inved(self, a, modulo):
        x, y = self.extgcd(a, modulo, 1)
        return (x+modulo)%modulo
    
    def root_manual(self):
        for i in range(self.cr):
            r = 1
            flg = True
            while flg:
                fflg = True
                for j in range(self.bl):
                    if self.doubling(r, self.bin_list[j], self.modulo_list[i]) == 1:
                        fflg = False
                if self.doubling(r, self.bin_list[-1], self.modulo_list[i]) != 1:
                    fflg = False
                if fflg:
                    flg = False
                else:
                    r += 1
                    if r >= self.modulo_list[i]:
                        break
            self.primal_root_list[i] = r
    
    def make_prime_root(self):
        cnt = 0
        j = 1
        last = self.bin_list[-1]
        while cnt < self.cr:
            if self.IsPrime(j*last+1):
                flg = True
                r = 1
                while flg:
                    fflg = True
                    for i in range(self.bl):
                        if self.doubling(r, self.bin_list[i], j*last+1) == 1:
                            fflg = False
                    if self.doubling(r, last, j*last+1) != 1:
                        fflg = False
                    if fflg:
                        flg = False
                    else:
                        r += 1
                        if r >= j*last+1:
                            break
                if flg==False:
                    self.modulo_list[cnt] = j*last+1
                    self.primal_root_list[cnt] = r
                    cnt += 1
            j += 2
    
    def make_basis(self):
        for i in range(self.cr):
            for j in range(self.bl):
                tmp = self.doubling(2, self.bl-j)
                self.primal_base_matrix[i][j] = self.doubling(self.primal_root_list[i], tmp, self.modulo_list[i])
                self.inverse_base_matrix[i][j] = self.inved(self.primal_base_matrix[i][j], self.modulo_list[i])
    
    def NTT(self, f, n, idx, depth, inverse=False, surface=True):
        mod = self.modulo_list[idx]
        i2 = self.inved(2, mod)
        i4 = self.inved(4, mod)
        if inverse:
            seed = self.primal_base_matrix[idx][depth]
        else:
            seed = self.inverse_base_matrix[idx][depth]
        if n == 1:
            return f
        if n == 2:
            xf = [(f[0] + f[1])%mod, (f[0] - f[1])%mod]
            if inverse * surface:
                xf[0] *= self.inved(2, mod)
                xf[0] %= mod
                xf[1] *= self.inved(2, mod)
                xf[1] %= mod
            return xf
        if n == 4:
            xf = [0, 0, 0, 0]
            s1, s2, s3 = seed, seed*seed%mod, seed*seed*seed%mod
            xf[0] = (f[0] + f[1] + f[2] + f[3]) % mod
            xf[1] = (f[0] + f[1]*s1%mod + f[2]*s2%mod + f[3]*s3%mod)%mod
            xf[2] = (f[0] + f[1]*s2%mod + f[2]*s2*s2%mod + f[3]*s3*s3%mod)%mod
            xf[3] = (f[0] + f[1]*s3%mod + f[2]*s3*s3%mod + f[3]*s3*s3*s3%mod)%mod
            if inverse * surface:
                for i in range(4):
                    xf[i] *= i4
                    xf[i] %= mod
            return xf
        hn = n // 2
        fe = [f[2*i+0] for i in range(hn)]
        fo = [f[2*i+1] for i in range(hn)]
        fe = self.NTT(fe, hn, idx, depth-1, inverse, False)
        fo = self.NTT(fo, hn, idx, depth-1, inverse, False)
        xf = [0 for _ in range(n)]
        grow = 1
        for i in range(hn):
            right = (fo[i] * grow) % mod
            xf[i+0*hn] = (fe[i] + right) % mod
            xf[i+1*hn] = (fe[i] - right) % mod
            grow *= seed
            grow %= mod
        if inverse * surface:
            invn = self.inved(n, mod)
            for i in range(n):
                xf[i] *= invn
                xf[i] %= mod
        return xf
    
    def CRT(self, num, a_list, m_list):
        r = a_list[0]
        bas = m_list[0]
        x, y = 0, 0
        for i in range(1, num):
            x, y = self.extgcd(bas, -m_list[i], -a_list[i]-r)
            r += bas * x
            bas *= m_list[i]
        return r % bas

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ntt = NTT(1, 23)
MOD = 998244353
ntt.modulo_list[0] = MOD
ntt.root_manual()
ntt.make_basis()
pl, cnt = ntt.powlimit(N+M)
A = A[:] + [0 for _ in range(pl-N)]
B = B[:] + [0 for _ in range(pl-M)]
X = ntt.NTT(A, pl, 0, cnt)
Y = ntt.NTT(B, pl, 0, cnt)
Z = [X[i]*Y[i]%MOD for i in range(pl)]
Z = ntt.NTT(Z, pl, 0, cnt, True)
for i in range(N+M-1):
    print(Z[i], end = ' '*(i!=N+M-2))
print()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.signal import convolve
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=object)
B = np.array(list(map(int, input().split())), dtype=object)
mod = 998244353
fft_len = 524288
C = convolve(A, B) % mod
print(*C[:N + M - 1].tolist(), sep='\n')

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=object)
B = np.array(list(map(int, input().split())), dtype=object)
mod = 998244353
fft_len = 524288
C = np.convolve(A, B) % mod
print(*C[:N + M - 1].tolist(), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# ----------- gcd ----------- #
def gcd(x, y):
    k, l = x, y
    if y < 0:
        k, l = -k, -l
    while l:
        k, l = l, k % l
    return k
    
def extgcd(a, b, c):
    if b == 0:
        return c // a, 0
    if b < 0:
        a, b, c = -a, -b, -c
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return c * x, c * y

# --------- IsPrime --------- #
def IsPrime(n):
    if n == 1:
        return False
    p = 2
    while p * p <= n:
        if n % p == 0:
            return False
        p += 1
    return True

# --- fraction calculator --- #
def fracsum(f1, f2, sign = 1):
    fs = [f1[0]*f2[1]+sign*f1[1]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs
def fracprod(f1, f2):
    fs = [f1[0]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs

# ------ factorization ------ #
def factorization(n):
    D = {}
    a = n
    p = 2
    while a != 1:
        cnt = 0
        while a % p == 0:
            cnt += 1
            a //= p
        if cnt != 0:
            D[p] = cnt
        p += 1
        if p * p > n and a != 1:
            D[a] = 1
            break
    return D
def divisors_list(D):
    F = [1]
    for i in D:
        mL = F[:]
        dp = i
        for j in range(D[i]):
            for k in mL:
                F.append(dp*k)
            dp *= i
    F.sort()
    return F

def doubling(n, m, modulo=0):
    y = 1
    base = n
    tmp = m
    while tmp:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo
def bic(n): # count time divided by 2
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt
def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        y *= 2
        cnt += 1
    return y, cnt
def CRT(n, a, b): # x = a[i] mod b[i]
    r = a[0]
    bas = b[0]
    x, y = 0, 0
    for i in range(1, n):
        x, y = extgcd(bas, -b[i], a[i] - r)
        r += bas * x
        bas *= b[i]
    return r % bas

# making lists of mod and prim. root
def mod_maker(cnt, num):
    bin_list = [1 for _ in range(cnt+1)]
    for i in range(cnt, 0, -1):
        bin_list[i-1] = 2*bin_list[i]
    L = []
    pm = []
    bas = doubling(2, cnt)
    ccnt = 0
    j = 1
    while ccnt < num:
        if IsPrime(j*bas+1):
            x = j*bas+1
            L.append(j*bas+1)
            ccnt += 1
            st = 1
            flg = 0
            while not flg:
                flg = (doubling(st, bin_list[0], x) == 1)
                for k in range(cnt):
                    flg *= (doubling(st, bin_list[k+1], x) != 1)
                if flg:
                    pm.append(st)
                    break
                st += 1
        j += 2
    return L, pm

def NTT(f, n, cn, num, inverse=False):
    if n == 1:
        return f
    if n == 2:
        return [(f[0]+f[1])%mod[num], (f[0]-f[1])%mod[num]]
    dn = n // 2
    fe = [f[2*i+0] for i in range(dn)]
    fo = [f[2*i+1] for i in range(dn)]
    fe = NTT(fe, dn, cn-1, num, inverse)
    fo = NTT(fo, dn, cn-1, num, inverse)
    seed = inverse * prim[num][cn] + (1 - inverse) * invp[num][cn]
    grow = 1
    xf = [0 for _ in range(n)]
    for i in range(dn):
        right = fo[i] * grow % mod[num]
        xf[i+0*dn] = (fe[i] + right) % mod[num]
        xf[i+1*dn] = (fe[i] - right) % mod[num]
        grow *= seed
        grow %= mod[num]
    return xf

# ----------- NTT test zone ----------- #
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pl, bn = powlimit(2*max(N, M)+2)
A = A[:] + [0]*(pl-N)
B = B[:] + [0]*(pl-M)
convolution_time = 1 # convolution level (number of 'mod's)
binary_count = 23
mod, primod = [998244353], [31]
prim = [[doubling(primod[j], doubling(2, binary_count-i), mod[j]) for i in range(binary_count)] for j in range(convolution_time)]
invp = [[inved(prim[j][i], mod[j]) for i in range(binary_count)] for j in range(convolution_time)]

X1 = NTT(A, pl, bn, 0)
X2 = NTT(B, pl, bn, 0)
XX = [X1[i]*X2[i]%mod[0] for i in range(pl)]
Y = NTT(XX, pl, bn, 0, 1)
ipl = inved(pl, mod[0])
for i in range(N+M-1):
    Y[i] *= ipl
    Y[i] %= mod[0]
    print(Y[i], end = ' '*(i!=N+M-2))
print()