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:
# 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]

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

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) % mod
  c = convolve_large(f2,g2,mod) % mod
  b = (convolve_large(f1+f2,g1+g2,mod) - (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

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

print(*convolve_large(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):
  f1,f2 = np.divmod(f,1<<15)
  g1,g2 = np.divmod(g,1<<15)
  
  a = convolve(f1,g1) % mod
  c = convolve(f2,g2) % mod
  b = (convolve(f1+f2,g1+g2) - (a+c)) % mod
  
  h = (a << 30) + (b << 15) + c
  return h % mod

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

Submission status: Wrong Answer

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# Modintの速度が遅い!!

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

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

def inv(x, m):
    if is_prime_constexpr(m):
        assert x
        return pow_(x, m - 2)
    else:
        eg = inv_gcd(x, m)
        assert eg[0] == 1
        return eg[2]

def pow_(x, n: int):
    assert 0 <= n
    r = 1
    while n:
        if n & 1: r = r*x%MOD
        x = x*x%MOD
        n >>= 1
    return r

def inv_gcd(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 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 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

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

# 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 = 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()
    ans = convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# Modintの速度が遅い!!

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

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

def inv(x, m):
    if is_prime_constexpr(m):
        assert x
        return pow_(x, m - 2)
    else:
        eg = inv_gcd(x, m)
        assert eg[0] == 1
        return eg[2]

def pow_(x, n: int):
    assert 0 <= n
    r = 1
    while n:
        if n & 1: r = r*x%MOD
        x = x*x%MOD
        n >>= 1
    return r

def inv_gcd(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 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 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

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

# 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 = 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()
    ans = convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# Modintの速度が遅い!!

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

def butterfly_inv(a: list):
    n = len(a)
    h = ceil_pow2(n)
    g = primitive_root(MOD)
    
    first = True
    sum_ie = [0] * 30
    if first:
        first = False
        es = [0] * 30; ies = [0] * 30
        cnt2 = bsf(MOD - 1)
        e = pow_(g, (MOD - 1) >> cnt2) % MOD; ie = inv(e, MOD) % 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):
            sum_ie[i] = es[i] * now % MOD
            now = ies[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] % MOD
                r = a[i + offset + p] % MOD
                a[i + offset] = (l + r) % MOD
                a[i + offset + p] = (MOD + l - r) * inow % MOD
            inow = sum_ie[bsf(~s)] * inow % MOD
    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] % MOD
        return ans
    z = 1 << ceil_pow2(n + m - 1)
    a = a + [0] * (z - len(a))
    a = butterfly(a)
    b = b + [0] * (z - len(b))
    b = butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    a = butterfly_inv(a)
    a = a[:n + m - 1]
    iz = inv(z, MOD)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= MOD
    return a
# modint.py
def inv(x, m):
    if is_prime_constexpr(m):
        assert x
        return pow_(x, m - 2)
    else:
        eg = inv_gcd(x, m)
        assert eg[0] == 1
        return eg[2]

def pow_(x, n: int):
    assert 0 <= n
    r = 1
    while n:
        if n & 1: r = r*x%MOD
        x = x*x%MOD
        n >>= 1
    return r

def inv_gcd(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 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 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

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

# 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 = 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()
    ans = convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

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 = 2**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=" ")

Submission status: Wrong Answer

Solution code:
ROOT = 3
MOD = 998244353

def w(k,n): # 1 の 2^n 乗根の k 乗
    return pow(ROOT,k*((MOD-1)>>n),MOD)

def ntt_rec(a,n):
    if n==0:
        return a[:]
    if n==1:
        return [a[0]+a[1],a[0]-a[1]]
            
    b = ntt_rec(a[::2],n-1)
    c = ntt_rec(a[1::2],n-1)
    
    N = 1<<(n-1)
    res = [0]*(N*2)
    for k in range(N):
        res[k]   = (b[k] + w(k,n)*c[k])%MOD
        res[k+N] = (b[k] - w(k,n)*c[k])%MOD
    return res

def intt_rec(a,n):
    res = ntt_rec(a[0:1]+a[1:][::-1],n)
    inv = pow(1<<n,MOD-2,MOD)
    for i in range(1<<n):
        res[i] = res[i]*inv%MOD
    return res


def convolution(a,b):
    deg = len(a) + len(b) - 1
    n = 0
    N = 1
    while deg*2 >= N:
        n += 1
        N <<= 1
    
    a += [0]*(N-len(a))
    b += [0]*(N-len(b))
    
    #print(ntt_rec(a,n))
    return intt_rec([ai*bi%MOD for ai,bi in zip(ntt_rec(a,n),ntt_rec(b,n))],n)

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

if n==1: print(1)

Submission status: Wrong Answer

Solution code:
def FFT(A):
    from math import sin,cos,exp,pi

    n=len(A)
    m=1
    while m<n:
        m<<=1
    w=complex(cos(2*pi/m),sin(2*pi/m))

    def fft(x):
        t=len(x)
        if t==1:
            return x

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

        w=complex(cos(2*pi/t),sin(2*pi/t))
        for k in range(t//2):
            y[k]=x[k]+x[k+t//2]
            z[k]=(x[k]-x[k+t//2])*(w**k)

        y=fft(y)
        z=fft(z)

        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 fft(B)

def Inverse_FFT(A):
    for i in range(len(A)):
        if isinstance(A[i],complex):
            A[i]=A[i].conjugate()

    G=FFT(A)
    for i in range(len(G)):
        if isinstance(G[i],complex):
            G[i]=G[i].conjugate()

    return [a/len(G) for a in G]

def Convolution(A,B,Mod=None):
    from math import floor

    N=len(A);M=len(B)
    if N==0 or M==0:
        return []

    z=1
    while z<N+M-1:
        z<<=1

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

    P=FFT(A)
    Q=FFT(B)

    R=[0]*z
    for i in range(z):
        R[i]=P[i]*Q[i]
    R=Inverse_FFT(R)
    return  [floor(a.real+1/2) for a in R]
#================================================
N,M=map(int,input().split())
Mod=998244353
A=list(map(int,input().split()))
B=list(map(int,input().split()))

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