A packet is a list of non-negative integer codes. The checksum of a block of codes is the bitwise XOR of all of them (a ^ b ^ ... in Python).
Choose a block codes[i..k] of at least two codes and cut it into a non-empty header codes[i..j-1] and a non-empty body codes[j..k], so i < j <= k. Count the choices of (i, j, k) for which the header and the body have the same checksum.
Examples
Input: codes = [3, 1, 2]
Output: 2
Explanation: [3] | [1, 2] gives 3 and 1 ^ 2 = 3; [3, 1] | [2] gives 2 and 2.
Input: codes = [5, 5]
Output: 1
Input: codes = [1, 2, 3, 4]
Output: 2
Explanation: the block [1, 2, 3] with either cut: 1 | 2 ^ 3 and 1 ^ 2 | 3.
Constraints
0 <= len(codes) <= 10**50 <= codes[i] < 2**20- Target complexity: O(n). Checking each block and cut, or even each block, is far too slow for the largest tests.
Goals
- Turn 'two neighbouring blocks have equal XOR' into 'two prefix XORs are equal'
- Count every split point of a block at once
- Keep a running sum of indices next to each count