For a given sequence of positive integers A1,A2,…,AN, you are supposed to find the number of triples (i,j,k) such that 1≤i<j≤k≤N and
Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,
where ⊕ denotes bitwise XOR.
Example Input
1
3
5 2 7
Example Output
2
Explanation
The triples are (1,3,3), since 5⊕2=7, and (1,2,3), since 5=2⊕7.
Constraints
1≤T≤10
2≤N≤10^5
1≤Ai≤10^6 for each valid i
Can someone explain me the approach please? thanks!
Do you know how to do truth tables? So, there's 5 = 101 and 2 = 010 so
1 2 3 4 5
|
5|2|?
_____
1|0|?
0|1|?
1|0|?
| |
Last edited on