Submission #1008596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008596		shikgom2	씽크스몰 (kriii3_TT)	Pypy 3	10 / 30	7693 ms	429076 KiB

tt

import sys
input = sys.stdin.readline
from functools import reduce
import operator

MOD = 998244353
ROOT = 3
IROOT = pow(ROOT, MOD-2, MOD)

def NTT(v, inv):
    S = len(v)
    j = 0
    for i in range(1, S):
        bit = S // 2
        while j >= bit:
            j -= bit
            bit //= 2
        j += bit
        if i < j:
            v[i], v[j] = v[j], v[i]
    
    k = 1
    while k < S:
        z = pow(ROOT if inv else IROOT, (MOD-1) // (2*k), MOD)
        i = 0
        while i < S:
            w = 1
            for j in range(k):
                even = v[i + j]
                odd = v[i + j + k] * w % MOD
                v[i + j] = (even + odd) % MOD
                v[i + j + k] = (even - odd + MOD) % MOD
                w = w * z % MOD
            i += k * 2
        k *= 2
    
    if inv:
        invS = pow(S, MOD-2, MOD)
        for i in range(S):
            v[i] = v[i] * invS % MOD

def mul(v, u):
    S = 2
    while S < len(v) + len(u):
        S *= 2
    vc = v + [0] * (S - len(v))
    uc = u + [0] * (S - len(u))
    NTT(vc, False)
    NTT(uc, False)
    for i in range(S):
        vc[i] = vc[i] * uc[i] % MOD
    NTT(vc, True)
    return vc

n, m = map(int, input().split())
a = [0] * 2000010
b = [0] * 2000010

a_input = list(map(int, input().split()))
b_input = list(map(int, input().split()))

a[:n+1] = a_input
b[:m+1] = b_input

aa = [x & ((1 << 10) - 1) for x in a]
bb = [x & ((1 << 10) - 1) for x in b]
ret22 = mul(aa, bb)

aa = [x >> 10 for x in a]
bb = [x & ((1 << 10) - 1) for x in b]
ret12 = mul(aa, bb)

aa = [x & ((1 << 10) - 1) for x in a]
bb = [x >> 10 for x in b]
ret21 = mul(aa, bb)

aa = [x >> 10 for x in a]
bb = [x >> 10 for x in b]
ret11 = mul(aa, bb)

ans = 0
max_len = min(len(ret11), len(ret21), len(ret12), len(ret22))
for i in range(max_len):
    ans ^= (ret11[i] << 20) + ((ret21[i] + ret12[i]) << 10) + ret22[i]

print(ans)

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