結果

問題 No.1142 XOR と XOR
ユーザー lam6er
提出日時 2025-04-15 23:48:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,353 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 154,584 KB
最終ジャッジ日時 2025-04-15 23:50:34
合計ジャッジ時間 5,402 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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