Range XOR - MarisaOJ: Marisa Online Judge

Range XOR

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $A$ consisting of $n$ integers. Count the number of contiguous subarrays such that the XOR sum of all elements in the subarray has an odd number of set bits. ### Input - The first line contains an integer $n$. - The second line contains $n$ integers $A_i$. ### Output - Print an integer, the number of contiguous subarrays satisfying the condition. ### Constraints - $1 \leq n \leq 10^6$. - $1 \leq A_i \leq 10^9$. ### Example Input: ``` 3 1 2 4 ``` Output: ``` 4 ```