You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC098D] Xor Sum 2

[ABC098D] Xor Sum 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题面翻译

给你一串数 $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)$

题目描述

長さ $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

样例输入 #1

4
2 5 4 6

样例输出 #1

5

样例 #2

样例输入 #2

9
0 0 0 0 0 0 0 0 0

样例输出 #2

45

样例 #3

样例输入 #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$ になります。