結果
問題 |
No.1493 隣接xor
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:22:02 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,527 bytes |
コンパイル時間 | 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 |
ソースコード
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()