結果

問題 No.1142 XOR と XOR
ユーザー lam6er
提出日時 2025-04-15 23:49:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 1,310 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 114,360 KB
最終ジャッジ日時 2025-04-15 23:51:31
合計ジャッジ時間 4,469 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def fwht_xor(a, invert):
    n = len(a)
    h = 1
    while h < n:
        for i in range(0, n, h * 2):
            for j in range(i, i + h):
                x = a[j]
                y = a[j + h]
                a[j] = (x + y) % MOD
                a[j + h] = (x - y) % MOD
                if invert:
                    a[j] = a[j] * 500000004 % MOD  # Modular inverse of 2
                    a[j + h] = a[j + h] * 500000004 % MOD
        h *= 2

def compute_counts(arr):
    F = [0] * 1024
    F[0] = 1  # Initial prefix XOR of 0
    pre = 0
    for num in arr:
        pre ^= num
        F[pre] = (F[pre] + 1) % MOD
    sum_F = sum(F) % MOD
    a = F.copy()
    fwht_xor(a, False)
    for i in range(1024):
        a[i] = a[i] * a[i] % MOD
    fwht_xor(a, True)
    count = [0] * 1024
    inv_2 = 500000004  # Precomputed inverse of 2 mod MOD
    for x in range(1024):
        if x == 0:
            count[x] = (a[x] - sum_F) * inv_2 % MOD
        else:
            count[x] = a[x] * inv_2 % MOD
    return count

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

count_a = compute_counts(a)
count_b = compute_counts(b)

ans = 0
for x in range(1024):
    y = x ^ K
    ans = (ans + count_a[x] * count_b[y]) % MOD

print(ans % MOD)
0