/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A があります。
次の条件を満たす整数 l, r ( 1 \leq l \leq r \leq N ) の組の個数を求めてください。
- A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r
xorの説明
整数 c_1, c_2, ..., c_m の xor は以下のように定義されます。
- xor の値を X とおく。X を 2 進数表記したときの 2^k ( 0 \leq k, k は整数 ) の位の値は、c_1, c_2, ...c_m のうち、2 進数表記したときの 2^k の位の値が 1 となるものが奇数個ならば 1、偶数個ならば 0 となる。
例えば、3 と 5 の xor の値は、3 の 2 進数表記が 011、5 の 2 進数表記が 101 のため、2 進数表記が 110 の 6 となります。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i < 2^{20}
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
条件を満たす整数 l, r ( 1 \leq l \leq r \leq N ) の組の個数を出力せよ。
入力例 1
4 2 5 4 6
出力例 1
5
明らかに、(l,r)=(1,1),(2,2),(3,3),(4,4) は条件を満たします。 また、(l,r)=(1,2) の場合、A_1\ xor\ A_2 = A_1\ +\ A_2 = 7 となるので、これも条件を満たします。 ほかに条件を満たす組はないので、答えは 5 になります。
入力例 2
9 0 0 0 0 0 0 0 0 0
出力例 2
45
入力例 3
19 885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1
出力例 3
37
Score : 500 points
Problem Statement
There is an integer sequence A of length N.
Find the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the following condition:
- A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r
Here, xor denotes the bitwise exclusive OR.
Definition of XOR
The XOR of integers c_1, c_2, ..., c_m is defined as follows:
- Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.
For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i < 2^{20}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the condition.
Sample Input 1
4 2 5 4 6
Sample Output 1
5
(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition. (l,r)=(1,2) also satisfies the condition, since A_1\ xor\ A_2 = A_1\ +\ A_2 = 7. There are no other pairs that satisfy the condition, so the answer is 5.
Sample Input 2
9 0 0 0 0 0 0 0 0 0
Sample Output 2
45
Sample Input 3
19 885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1
Sample Output 3
37