732. Counting Stretches That XOR to k
Count the contiguous stretches whose bitwise XOR is exactly k.
4 2 2 6 4, k = 6 -> 4
5 6 7 8 9, k = 5 -> 2
2 2 2 2, k = 0 -> 4
1 2 3, k = 0 -> 1
## Rearranging the condition
With P[i] the XOR of the first i values, the stretch from i+1 to j has XOR
P[j] ^ P[i]. So the condition is
P[j] ^ P[i] == k
XOR both sides by P[j], and because P[j] ^ P[j] is 0:
P[i] == P[j] ^ k
So for each right end j, the number of qualifying left ends is exactly how many earlier
prefixes equal P[j] ^ k. Keep a tally of prefixes seen so far and look that value up.
This is problem 286 with addition replaced by XOR. There, S[j] - S[i] == k rearranges to
S[i] == S[j] - k. Here the rearrangement uses XOR's self-inverse property instead of
subtraction, and the rest of the method is identical.
## Seed the tally with one zero
Before the sweep, record that the prefix 0 has been seen once. That empty prefix is what allows a stretch STARTING at position 1 to be counted, and forgetting it loses exactly those.
On 1 2 3 with k = 0 the answer is 1, from the whole array, and the whole array is a stretch
starting at position 1. Without the seed the answer comes out 0.
This is the single most common error in the prefix-plus-map family, and it is the same one problem 286 and problem 301 warn about.
## Look up BEFORE inserting
Update the running prefix, look up P ^ k, and only then record the new prefix.
Inserting first lets a stretch pair with itself. With k = 0 that adds one bogus stretch per
position, because P ^ 0 is P, so on 2 2 2 2 the answer becomes 8 instead of 4.
The two errors above are opposite in sign, and an implementation with both can pass small tests by accident. That is why both cases are in the test set.
## Overflow
The count reaches 2 * 10^10, past a signed 32 bit integer, even though nothing else here
does.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 10^9` - `0 ≤ each value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of stretches whose XOR is k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.