oj.uz

Submission #1008596

# Submission time Handle Problem Language Result Execution time Memory
1008596 2024-06-26T15:06:25 Z shikgom2 씽크스몰 (kriii3_TT) PyPy 3
10 / 30
 7693 ms 429076 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7458 ms 412944 KB Output is correct
2 Correct 7086 ms 412620 KB Output is correct
3 Correct 7421 ms 412580 KB Output is correct
4 Correct 7282 ms 412584 KB Output is correct
5 Correct 6942 ms 412712 KB Output is correct
6 Correct 7518 ms 412600 KB Output is correct
7 Correct 7294 ms 412596 KB Output is correct
8 Correct 7504 ms 412620 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7645 ms 412756 KB Output is correct
2 Correct 7629 ms 415340 KB Output is correct
3 Correct 7672 ms 417280 KB Output is correct
4 Correct 7682 ms 385360 KB Output is correct
5 Correct 7693 ms 390972 KB Output is correct
6 Correct 7401 ms 423964 KB Output is correct
7 Correct 7557 ms 391992 KB Output is correct
8 Incorrect 7556 ms 390992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7149 ms 429076 KB Output isn't correct
2 Halted 0 ms 0 KB -