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:
import numpy as np

def convolve(f,g):
    fft_len = 1
    while fft_len < len(f)+len(g)-1:
        fft_len *= 2
    Ff = np.fft.rfft(f,fft_len)
    Fg = np.fft.rfft(g,fft_len)
    Fh = Ff*Fg
    h = np.fft.irfft(Fh,fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:len(f)+len(g)-1]

def convolve2(f,g,p):
    f1,f2 = np.divmod(f,1 << 15)
    g1,g2 = np.divmod(g,1 << 15)

    a = convolve(f1,g1) % p
    c = convolve(f2,g2) % p
    b = (convolve(f1+f2,g1+g2)-(a+c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p

mod = 998244353
N,M = map(int,input().split())
a = np.array(list(map(int,input().split())),dtype=np.longdouble)
b = np.array(list(map(int,input().split())),dtype=np.longdouble)
c = convolve2(a,b,mod)
print(*c)

Submission status: Wrong Answer

Solution code:
import numpy as np

def convolve(f,g):
    fft_len = 1
    while fft_len < len(f)+len(g)-1:
        fft_len *= 2
    Ff = np.fft.rfft(f,fft_len)
    Fg = np.fft.rfft(g,fft_len)
    Fh = Ff*Fg
    h = np.fft.irfft(Fh,fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:len(f)+len(g)-1]

def convolve2(f,g,p):
    f1,f2 = np.divmod(f,1 << 15)
    g1,g2 = np.divmod(g,1 << 15)

    a = convolve(f1,g1) % p
    c = convolve(f2,g2) % p
    b = (convolve(f1+f2,g1+g2)-(a+c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p

mod = 998244353
N,M = map(int,input().split())
a = np.array(list(map(int,input().split())))
b = np.array(list(map(int,input().split())))
c = convolve2(a,b,mod)
print(*c)

Submission status: Wrong Answer

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]
        prr = self.primal_base_matrix[idx][depth]
        if n == 1:
            return f
        if n == 2:
            xf = [(f[0] + f[1])%mod, (f[0] - f[1])%mod]
            if depth * surface:
                xf[0] *= self.inved(2, mod)
                xf[0] %= mod
                xf[1] *= self.inved(2, mod)
                xf[1] %= 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
        if inverse:
            seed = self.primal_base_matrix[idx][depth]
        else:
            seed = self.inverse_base_matrix[idx][depth]
        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 *= b[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: Wrong Answer

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


from cmath import pi,exp


def dfs(f,start,step,N,inverse=False):
    if N == 2:
        a,b = f[start],f[start+step]
        return [a+b,a-b]
    if inverse is False:
        f0 = dfs(f,start,2*step,N//2,inverse=False)
        f1 = dfs(f,start+step,2*step,N//2,inverse=False)
        z = exp(2j*pi/N)
    else:
        f0 = dfs(f,start,2*step,N//2,inverse=True)
        f1 = dfs(f,start+step,2*step,N//2,inverse=True)
        z = exp(-2j*pi/N)
    z0 = 1.0
    for i in range(N//2):
        a,b = f0[i],f1[i]*z0
        f0[i],f1[i] = a+b,a-b
        z0 *= z
    return f0+f1


def DFT(f,N):  # fを離散フーリエ変換
    if N == 1:
        return f
    return dfs(f,0,1,N)


def iDFT(F,N):  # Fを離散フーリエ逆変換
    if N == 1:
        return F
    f = dfs(F,0,1,N,inverse=True)
    for i in range(N):
        f[i] /= N
    return f


# deg(f)+deg(g)<Nとなる2冪Nを選び、f,gの長さがNになるように0を埋めておく


def product(f,g,N):  # 多項式f,gの積
    F = DFT(f,N)
    G = DFT(g,N)
    FG = [F[i]*G[i] for i in range(N)]
    fg = iDFT(FG,N)
    for i in range(N):
        fg[i] = int(fg[i].real+0.5) % mod
    return fg


N,M = MI()
A,B = LI(),LI()
mod = 998244353
R = 1 << (N+M-2).bit_length()
A += [0]*(R-N)
B += [0]*(R-M)

ANS = product(A,B,R)
print(*ANS[:N+M-1])

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=[167772161,469762049,1224736769]
def NTT167772161(a):
  n=len(a)
  h=pow(3,(167772161-1)//n,167772161)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,167772161)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%167772161
        a[s]=u+d
        if a[s]>=167772161:
          a[s]-=167772161
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=167772161
        s+=(m<<1)
      w=w*base%167772161
    m<<=1

def NTT469762049(a):
  n=len(a)
  h=pow(3,(469762049-1)//n,469762049)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,469762049)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%469762049
        a[s]=u+d
        if a[s]>=469762049:
          a[s]-=469762049
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=469762049
        s+=(m<<1)
      w=w*base%469762049
    m<<=1

def NTT1224736769(a):
  n=len(a)
  h=pow(3,(1224736769-1)//n,1224736769)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,1224736769)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%1224736769
        a[s]=u+d
        if a[s]>=1224736769:
          a[s]-=1224736769
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=1224736769
        s+=(m<<1)
      w=w*base%1224736769
    m<<=1

def NTT167772161inv(a):
  n=len(a)
  h=pow(3,(167772161-1)//n,167772161)
  h=pow(h,167772161-2,167772161)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,167772161)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%167772161
        a[s]=u+d
        if a[s]>=167772161:
          a[s]-=167772161
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=167772161
        s+=(m<<1)
      w=w*base%167772161
    m<<=1

def NTT469762049inv(a):
  n=len(a)
  h=pow(3,(469762049-1)//n,469762049)
  h=pow(h,469762049-2,469762049)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,469762049)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%469762049
        a[s]=u+d
        if a[s]>=469762049:
          a[s]-=469762049
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=469762049
        s+=(m<<1)
      w=w*base%469762049
    m<<=1

def NTT1224736769inv(a):
  n=len(a)
  h=pow(3,(1224736769-1)//n,1224736769)
  h=pow(h,1224736769-2,1224736769)
  i=0
  k=0
  for j in range(1,n-1):
    k=(n>>1)
    i^=k
    while k>i:
      k>>=1
      i^=k
    if j<i:
      a[i],a[j]=a[j],a[i]
  m=1
  l=n
  s,u,d=0,0,0
  while m<n:
    l>>=1
    base=pow(h,l,1224736769)
    w=1
    for x in range(m):
      s=x
      while s<n:
        u=a[s]
        d=a[s+m]*w%1224736769
        a[s]=u+d
        if a[s]>=1224736769:
          a[s]-=1224736769
        a[s+m]=u-d
        if a[s+m]<0:
          a[s+m]+=1224736769
        s+=(m<<1)
      w=w*base%1224736769
    m<<=1

def convolution167772161(a,b):
  siz=1
  while siz<len(a)+len(b):
    siz<<=1
  aa=a[:]
  bb=b[:]
  while len(aa)<siz:
    aa.append(0)
  while len(bb)<siz:
    bb.append(0)
  NTT167772161(aa)
  NTT167772161(bb)
  for i in range(siz):
    aa[i]=aa[i]*bb[i]%167772161
  NTT167772161inv(aa)
  v=pow(siz,167772161-2,167772161)
  for i in range(siz):
    aa[i]=aa[i]*v%167772161
  return aa

def convolution469762049(a,b):
  siz=1
  while siz<len(a)+len(b):
    siz<<=1
  aa=a[:]
  bb=b[:]
  while len(aa)<siz:
    aa.append(0)
  while len(bb)<siz:
    bb.append(0)
  NTT469762049(aa)
  NTT469762049(bb)
  for i in range(siz):
    aa[i]=aa[i]*bb[i]%469762049
  NTT469762049inv(aa)
  v=pow(siz,469762049-2,469762049)
  for i in range(siz):
    aa[i]=aa[i]*v%469762049
  return aa

def convolution1224736769(a,b):
  siz=1
  while siz<len(a)+len(b):
    siz<<=1
  aa=a[:]
  bb=b[:]
  while len(aa)<siz:
    aa.append(0)
  while len(bb)<siz:
    bb.append(0)
  NTT1224736769(aa)
  NTT1224736769(bb)
  for i in range(siz):
    aa[i]=aa[i]*bb[i]%1224736769
  NTT1224736769inv(aa)
  v=pow(siz,1224736769-2,1224736769)
  for i in range(siz):
    aa[i]=aa[i]*v%1224736769
  return aa

def CONVOLUTION(a,b,mod):
  x=convolution167772161(a,b)
  y=convolution469762049(a,b)
  z=convolution1224736769(a,b)
  inv1=pow(167772161,469762049-2,469762049)
  inv12=pow(167772161*469762049,1224736769-2,1224736769)
  m12=167772161*469762049%1224736769
  v1,v2,c3=0,0,0
  r=[0]*len(x)
  for i in range(len(x)):
    v1=(y[i]-x[i])*inv1%469762049
    v2=(z[i]-(x[i]+v1*167772161)%1224736769)*inv12%1224736769
    c3=(x[i]+167772161*v1+m12*v2)%mod
    r[i]=c3
  return r

print(*CONVOLUTION(A,B,998244353)[:N+M-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

input = sys.stdin.readline


def convolve(f, g):
    fft_len = 1
    while 2 * fft_len < len(f) + len(g) - 1:
        fft_len *= 2
    fft_len *= 2

    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)

    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)

    h = np.rint(h).astype(np.int64)

    return h[:len(f) + len(g) - 1]


def convolve2(f, g, mod=998244353):
    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


def main():
    n, m = map(int, input().split())
    a = np.array(input().split(), np.int64)
    b = np.array(input().split(), np.int64)
    c = convolve2(a, b)
    print(*c)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import scipy
import scipy.signal

_ = input()
print(*scipy.signal.convolve(list(map(int, input().split())), list(map(int, input().split()))) % 998244353)

Submission status: Wrong Answer

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

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)
  
N,M=map(int,input().split())
*a,=map(int,input().split())
*b,=map(int,input().split())

print(*convolve(a,b)[:N+M-1] %mod)

Submission status: Wrong Answer

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.round(np.real(np.fft.irfft(np.fft.fft(A, fft_len) * np.fft.fft(B, fft_len), fft_len))).astype(np.int64) % mod

print(*C[:N + M - 1].tolist(), sep='\n')

Submission status: Wrong Answer

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

x = irfft(rfft(A, fft_len) * rfft(B, fft_len))

for i in x[:N + M - 1]:
    print(int(i + .5) % mod)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
import numpy as np
import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))
clst = np.convolve(alst, blst)
ans = [c % MOD for c in clst]
print(*ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
import numpy as np
n, m = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))
clst = np.convolve(alst, blst)
ans = [c % MOD for c in clst]
print(*ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))
c = np.convolve(alst, blst)
print(*c)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
AS = np.array(list(map(int, input().split())), dtype=np.int64)
BS = np.array(list(map(int, input().split())), dtype=np.int64)
cs = np.convolve(AS, BS)
cs %= 998244353
print(*cs, sep=" ")

Submission status: Wrong Answer

Solution code:
from math import sin, cos, pi
from collections import deque

mod = 998244353

def DFT(A, inv = False):
    if inv:
        sgn = -1
    else:
        sgn = 1
    Q1 = deque()
    Q2 = deque()
    sz = len(A)
    Q1.append((A,0))
    while len(Q1) > 0:
        A,f = Q1.pop()
        sz = len(A)
        if sz==1:
            Q2.append(A)
            continue
        if f==0:
            A0 = [A[2*i] for i in range(sz//2)]
            A1 = [A[2*i+1] for i in range(sz//2)]    
            Q1.append((A,1))
            Q1.append((A1,0))
            Q1.append((A0,0))
        else:
            A1 = Q2.pop()
            A0 = Q2.pop()
            now = 1
            zeta = complex(cos(2*sgn*pi/sz), sin(2*sgn*pi/sz))
            for i in range(sz):
                A[i] = A0[i % (sz//2)] + now * A1[i % (sz//2)]
                now *= zeta
            Q2.append(A)


def convolution(A, B):
    sz = 1
    while sz<len(A)+len(B):
        sz *= 2
    
    nA = [0]*sz
    nB = [0]*sz
    
    for i, a in enumerate(A):
        nA[i] = a

    for i, b in enumerate(B):
        nB[i] = b

    DFT(nA)
    DFT(nB)

    for i in range(sz):
        nA[i] *= nB[i]
    
    DFT(nA, inv=True) 

    res = [round(a.real/sz)%mod for a in nA]
    return res   

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = convolution(A,B)
    print(*C[:N+M-1])
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import sin, cos, pi
from collections import deque

mod = 998244353

def DFT(A, inv = False):
    if inv:
        sgn = -1
    else:
        sgn = 1
    Q1 = deque()
    Q2 = deque()
    sz = len(A)
    Q1.append((A,0))
    while len(Q1) > 0:
        A,f = Q1.pop()
        sz = len(A)
        if sz==1:
            Q2.append(A)
            continue
        if f==0:
            A0 = [A[2*i] for i in range(sz//2)]
            A1 = [A[2*i+1] for i in range(sz//2)]    
            Q1.append((A,1))
            Q1.append((A1,0))
            Q1.append((A0,0))
        else:
            A1 = Q2.pop()
            A0 = Q2.pop()
            now = 1
            zeta = complex(cos(2*sgn*pi/sz), sin(2*sgn*pi/sz))
            for i in range(sz):
                A[i] = A0[i % (sz//2)] + now * A1[i % (sz//2)]
                now *= zeta
            Q2.append(A)


def convolution(A, B):
    sz = 1
    while sz<len(A)+len(B):
        sz *= 2
    
    nA = [0]*sz
    nB = [0]*sz
    
    for i, a in enumerate(A):
        nA[i] = a

    for i, b in enumerate(B):
        nB[i] = b

    DFT(nA)
    DFT(nB)

    for i in range(sz):
        nA[i] *= nB[i]
    
    DFT(nA, inv=True) 

    res = [round(a.real/sz)%mod for a in nA]
    return res   

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = convolution(A,B)
print(*C[:N+M-1])

Submission status: Wrong Answer

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

from numpy import*
a=array(A)
b=array(B)
C=convolve(a,b)

M=998244353
for c in C:
    print(c%M,end=' ')
print()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    from builtins import int,map
    import numpy as np
    r=stdin.readline
    n,m=map(int,r().split())
    a=np.array(list(map(int,r().split())),dtype='uint64')
    b=np.array(list(map(int,r().split())),dtype='uint64')
    c=np.convolve(a,b)
    for i in c:
        print(int(i%998244353),end=" ")
main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    import numpy as np
    r=stdin.readline
    n,m=map(int,r().split())
    a=np.array(list(map(int,r().split())),dtype='int64')
    b=np.array(list(map(int,r().split())),dtype='int64')
    c=np.convolve(a,b)
    for i in c:
        print(i%998244353,end=" ")
main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 30000
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)[:n+m-1]
write(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 40000
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)[:n+m-1]
write(" ".join(map(str, c)))

Submission status: Wrong Answer

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

N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inv = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inv[i]) % mod )
inv[0]=0

def _ntt(f,L,reverse=False):
    F=[f[i] for i in range(L)]
    n = L.bit_length() - 1
    base = omega
    if reverse:
        base = rev_omega

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

    for i in range(n,0,-1):
        use_omega = pow(base,2**(22+i-n),mod)
        res = [0]*2**n
        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

def ntt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L)
    return F

def intt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    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

def convolve(f,g,limit):
    l = len(f)+len(g)-1
    L = 1<<((l-1).bit_length())

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

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

    h = intt(H,L)

    return h[:limit]

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

print(*convolve(a,b,N+M-1))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
a=np.array(list(map(int,input().split())),dtype='uint64')
b=np.array(list(map(int,input().split())),dtype='uint64')
c=np.convolve(a,b)
for i in c:
    print(i%998244353,end=" ")

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
pin=sys.stdin.readline
pout=sys.stdout.write

N,M=map(int,pin().split())
a=list(map(int,pin().split()))
arr1=np.array(a)
b=list(map(int,pin().split()))
arr2=np.array(b)
c=np.convolve(arr1,arr2)
for i in range(N+M-1):
  pout(f"{c[i]%998244353} ")
print()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
pin=sys.stdin.readline
pout=sys.stdout.write

N,M=map(int,pin().split())
a=list(map(int,pin().split()))
arr1=np.array(a)
b=list(map(int,pin().split()))
arr2=np.array(b)
c=np.convolve(arr1,arr2)
for i in c:
  pout(f"{i%998244353} ")
print()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 1<<18
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)[:n+m-1]
write(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 1<<20
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)[:n+m-1]
write(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 1<<15
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)[:n+m-1]
write(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
pin=sys.stdin.readline
pout=sys.stdout.write

N,M=map(int,pin().split())
a=list(map(int,pin().split()))
arr1=np.array(a)
b=list(map(int,pin().split()))
arr2=np.array(b)
c=np.convolve(arr1,arr2)
for i in c:
  pout(f"{i} ")
print()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = pow(2, max(len(a)-1,len(b)-1).bit_length())
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = np.rint(c).astype(np.int64)
    return c
def fft_large(a,b):
    d = 1<<15
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)
write(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# FFT
import numpy as np
M = 998244353
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
def fft(a,b):
    l = pow(2, max(len(a)-1,len(b)-1).bit_length())
    c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
    c = (c.real+0.1).astype(np.int64)
    return c
def fft_large(a,b):
    d = 1<<15
    a1, a2 = np.divmod(a,d)
    b1, b2 = np.divmod(b,d)
    aa = fft(a1,b1) % M
    bb = fft(a2,b2) % M
    cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
    h = (((aa*d)%M)*d  + cc*d + bb) % M
    return h
c = fft_large(a,b)
write(" ".join(map(str, c)))