結果

問題 No.1142 XOR と XOR
ユーザー lam6er
提出日時 2025-03-20 21:11:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,853 bytes
コンパイル時間 460 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 163,444 KB
最終ジャッジ日時 2025-03-20 21:11:12
合計ジャッジ時間 4,951 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 2 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    a = list(map(int, input[idx:idx+N]))
    idx +=N
    b = list(map(int, input[idx:idx+M]))
    idx +=M
    
    # Compute prefix XOR for a
    pre_a = [0] * (N+1)
    for i in range(1, N+1):
        pre_a[i] = pre_a[i-1] ^ a[i-1]
    
    # Compute prefix XOR for b
    pre_b = [0] * (M+1)
    for i in range(1, M+1):
        pre_b[i] = pre_b[i-1] ^ b[i-1]
    
    # Calculate counter_a
    counter_a = [0] * 1024
    map_a = [0] * 1024
    map_a[pre_a[0]] += 1  # pre_a[0] =0
    for i in range(1, N+1):
        current = pre_a[i]
        temp_counter = [0] * 1024
        for x in range(1024):
            if map_a[x] == 0:
                continue
            xor_val = current ^ x
            temp_counter[xor_val] += map_a[x]
        # Update counter_a
        for x in range(1024):
            counter_a[x] = (counter_a[x] + temp_counter[x]) % MOD
        # Update map_a
        map_a[current] += 1
    
    # Calculate counter_b
    counter_b = [0] * 1024
    map_b = [0] * 1024
    map_b[pre_b[0]] += 1  # pre_b[0] =0
    for i in range(1, M+1):
        current = pre_b[i]
        temp_counter = [0] * 1024
        for x in range(1024):
            if map_b[x] == 0:
                continue
            xor_val = current ^ x
            temp_counter[xor_val] += map_b[x]
        # Update counter_b
        for x in range(1024):
            counter_b[x] = (counter_b[x] + temp_counter[x]) % MOD
        # Update map_b
        map_b[current] += 1
    
    # Calculate the answer
    ans = 0
    for x in range(1024):
        y = x ^ K
        ans = (ans + counter_a[x] * counter_b[y]) % MOD
    print(ans % MOD)

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