Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3656

Problem Lang User Status Time Memory
Convolution pypy3 toyuzuko AC 2228 ms 214.04 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1672 ms 120.01 MiB
example_01 AC 1659 ms 119.63 MiB
fft_killer_00 AC 2228 ms 212.45 MiB
fft_killer_01 AC 2227 ms 212.89 MiB
max_random_00 AC 2220 ms 214.04 MiB
max_random_01 AC 2222 ms 213.29 MiB
medium_00 AC 1677 ms 120.68 MiB
medium_01 AC 1689 ms 120.14 MiB
medium_02 AC 1747 ms 120.20 MiB
random_00 AC 2118 ms 208.90 MiB
random_01 AC 2148 ms 181.01 MiB
random_02 AC 1917 ms 161.72 MiB
small_00 AC 1673 ms 119.59 MiB
small_01 AC 1667 ms 119.64 MiB
small_02 AC 1657 ms 119.70 MiB
small_03 AC 1668 ms 119.64 MiB
small_04 AC 1686 ms 119.59 MiB
small_05 AC 1658 ms 119.64 MiB
small_06 AC 1677 ms 119.61 MiB
small_07 AC 1668 ms 119.59 MiB
small_08 AC 1657 ms 119.71 MiB
small_09 AC 1645 ms 119.60 MiB
small_10 AC 1647 ms 119.68 MiB
small_11 AC 1670 ms 119.71 MiB
small_12 AC 1704 ms 119.61 MiB
small_13 AC 1664 ms 119.62 MiB
small_14 AC 1648 ms 119.68 MiB
small_15 AC 1663 ms 119.68 MiB

class FastModuloTransform(): def __init__(self,omega,n,mod): self.n = n self.omega = omega self.mod = mod self.rev = pow(omega,mod-2,mod) def _bit_reverse_(self,d): n = len(d) ns = n>>1 nss = ns>>1 ns1 = ns+1 i = 0 for j in range(0,ns,2): if j<i: d[i],d[j] = d[j],d[i] d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1] d[i+1],d[j+ns] = d[j+ns],d[i+1] k = nss i ^= k while k > i: k >>= 1 i ^= k return d def _fmt_(self,A,base): halfpow = pow(base,self.n//2,self.mod) n = self.n m = 1 while n > 1: n >>= 1 w = pow(base,n,self.mod) wk = 1 for j in range(m): for i in range(j,self.n,2*m): U = A[i] V = (A[i+m]*wk)%self.mod A[i] = (U+V)%self.mod A[i+m] = (U+V*halfpow)%self.mod wk = (wk*w)%self.mod m <<= 1 return A def fmt(self,f): A = f+[0]*(self.n-len(f)) self._bit_reverse_(A) F = self._fmt_(A,self.omega) return F def ifmt(self,F): A = F+[0]*(self.n-len(F)) self._bit_reverse_(A) nrev = pow(self.n,self.mod-2,self.mod) f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)] return f def convolute(self,f,g): F = self.fmt(f) G = self.fmt(g) H = [(s*t)%self.mod for s,t in zip(F,G)] h = self.ifmt(H) return h MOD = 2**23*7*17+1 # 998244353 N,M = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) fmt = FastModuloTransform(646,2**20,MOD) C = fmt.convolute(A,B) print(' '.join(map(str,C[:N+M-1])))