結果

問題 No.1493 隣接xor
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:22:02
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,527 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 393 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 577,056 KB
最終ジャッジ日時 2025-05-14 13:24:21
合計ジャッジ時間 4,382 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def main():
    N = int(sys.stdin.readline())
    A_str = sys.stdin.readline().split()
    A = [int(x) for x in A_str]

    if N == 0:
        print(0)
        return
    
    MOD = 10**9 + 7

    # prefix_xor[i] stores A[0] ^ A[1] ^ ... ^ A[i-1]
    # prefix_xor[0] = 0 (empty prefix XOR sum)
    prefix_xor = [0] * (N + 1)
    current_xor_sum = 0
    for i in range(N):
        current_xor_sum ^= A[i]
        prefix_xor[i+1] = current_xor_sum
    
    # dp[k] will store the set of unique sequences formed from A[0...k-1]
    # where the last segment ends at A[k-1] (meaning prefix_xor[k] is the
    # cumulative XOR sum for this point).
    dp = [set() for _ in range(N + 1)]
    
    # Base case: for an empty prefix A[0...-1] (represented by prefix_xor[0]),
    # the only sequence is an empty tuple.
    dp[0] = {()}

    for k_idx in range(1, N + 1): # k_idx corresponds to prefix_xor[k_idx]
        for prev_k_idx in range(k_idx):
            # The current segment is A[prev_k_idx ... k_idx-1].
            # Its XOR sum is prefix_xor[k_idx] ^ prefix_xor[prev_k_idx].
            segment_val = prefix_xor[k_idx] ^ prefix_xor[prev_k_idx]
            
            # For each sequence that ended at prefix_xor[prev_k_idx],
            # append the new segment_val.
            for seq_prefix in dp[prev_k_idx]:
                new_sequence = seq_prefix + (segment_val,)
                dp[k_idx].add(new_sequence)
        
    result = len(dp[N]) % MOD
    print(result)

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