[ABC098D] Xor Sum 2
题意翻译
给你一串数 $a$
求出满足$a_l+\cdots +a_r=a_l\operatorname{xor}\cdots\operatorname{xor}a_r,l\le r$ 的 $(i,j)$ 的数量
$1\le n\le 200000,\forall 1\le i\le n,0\le a_i<2^{20}(1048576)$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc098/tasks/arc098_b
長さ $ 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 $ となります。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
条件を満たす整数 $ l $, $ r $ ( $ 1\ \leq\ l\ \leq\ r\ \leq\ N $ ) の組の個数を出力せよ。
输入输出样例
输入样例 #1
4
2 5 4 6
输出样例 #1
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
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 0\ \leq\ A_i $
- 入力はすべて整数である
### Sample Explanation 1
明らかに、$ (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 $ になります。