Submission #1086414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086414		shikgom2	씽크스몰 (kriii3_TT)	Pypy 3	20 / 30	1139 ms	164296 KiB

tt

import sys
input = sys.stdin.readline
import cmath
import math

def fft(a, inv):
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j >= bit:
            j -= bit
            bit >>= 1
        j += bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    
    angle = -2 * math.pi if inv else 2 * math.pi
    length = 2
    while length <= n:
        w = [cmath.exp(angle / length * i * 1j) for i in range(length // 2)]
        for i in range(0, n, length):
            for j in range(length // 2):
                u = a[i + j]
                v = a[i + j + length // 2] * w[j]
                a[i + j] = u + v
                a[i + j + length // 2] = u - v
        length <<= 1

    if inv:
        for i in range(n):
            a[i] /= n

def multiply(a, b):
    fa = [complex(x) for x in a]
    fb = [complex(x) for x in b]
    n = 1
    while n < max(len(a), len(b)):
        n <<= 1
    fa += [0] * (n - len(fa))
    fb += [0] * (n - len(fb))

    fft(fa, False)
    fft(fb, False)
    fa = [x * y for x, y in zip(fa, fb)]
    fft(fa, True)
    return [int(x.real + (0.5 if x.real > 0 else -0.5)) for x in fa]

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

n += 1
m += 1
k = 1
while k < 2 * max(n, m) - 1:
    k <<= 1
a += [0] * (k - len(a))
b += [0] * (k - len(b))

res = multiply(a, b)
ans = 0
for x in res[:n + m - 1]:
    ans ^= x
print(ans)

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10