結果

問題 No.1142 XOR と XOR
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:50:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,353 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 154,652 KB
最終ジャッジ日時 2025-04-15 23:52:39
合計ジャッジ時間 5,215 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    a = list(map(int, data[idx:idx+N]))
    idx += N
    b = list(map(int, data[idx:idx+M]))
    idx += M
    
    # Compute cnt_a for array a
    count_a = [0] * 1024
    count_a[0] = 1
    current_xor = 0
    cnt_a = [0] * 1024
    for num in a:
        current_xor ^= num
        for x in range(1024):
            if count_a[x]:
                A = current_xor ^ x
                cnt_a[A] = (cnt_a[A] + count_a[x]) % MOD
        count_a[current_xor] = (count_a[current_xor] + 1) % MOD
    
    # Compute cnt_b for array b
    count_b = [0] * 1024
    count_b[0] = 1
    current_xor = 0
    cnt_b = [0] * 1024
    for num in b:
        current_xor ^= num
        for x in range(1024):
            if count_b[x]:
                B = current_xor ^ x
                cnt_b[B] = (cnt_b[B] + count_b[x]) % MOD
        count_b[current_xor] = (count_b[current_xor] + 1) % MOD
    
    # Calculate the answer
    ans = 0
    for A in range(1024):
        target = A ^ K
        if target >= 1024:
            continue
        ans = (ans + cnt_a[A] * cnt_b[target]) % MOD
    
    print(ans % MOD)

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