結果

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

ソースコード

diff # 

import sys

MOD = 10**9 + 7

def compute_freq(arr):
    prefix_xor = [0]
    for num in arr:
        prefix_xor.append(prefix_xor[-1] ^ num)
    cnt = [0] * 1024
    for x in prefix_xor:
        cnt[x] += 1
    freq = [0] * 1024
    # Compute for x=0
    total = 0
    for c in range(1024):
        total += cnt[c] * (cnt[c] - 1) // 2
    freq[0] = total
    # Compute for x=1..1023
    for x in range(1, 1024):
        total = 0
        for c in range(1024):
            total += cnt[c] * cnt[c ^ x]
        freq[x] = total // 2
    return freq

def main():
    N, M, K = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))
    
    freq_a = compute_freq(a)
    freq_b = compute_freq(b)
    
    ans = 0
    for x in range(1024):
        y = x ^ K
        if y < 1024:
            ans = (ans + freq_a[x] * freq_b[y]) % MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()
0