AT_arc098_b [ABC098D] Xor Sum 2

题目描述

有一个长度为 $N$ 的整数序列 $A$。

请你求出满足以下条件的整数对 $(l, r)$ 的个数（$1 \leq l \leq r \leq N$）：

• $A_l \operatorname{xor} A_{l+1} \operatorname{xor} \cdots \operatorname{xor} A_r = A_l + A_{l+1} + \cdots + A_r$

:::info[$\operatorname{xor}$ 的定义]

对于整数 $c_1, c_2, \ldots, c_m$，它们的 $\operatorname{xor}$ 定义如下：

• 设 $xor$ 的值为 $X$。将 $X$ 用二进制表示时，对于每一个 $2^k$ 位（$0 \leq k$，$k$ 为整数），如果 $c_1, c_2, \ldots, c_m$ 中在该位为 $1$ 的数的个数为奇数，则 $X$ 的该位为 $1$，否则为 $0$。

例如，$3$ 和 $5$ 的 $xor$ 值为 $6$，因为 $3$ 的二进制为 $011$，$5$ 的二进制为 $101$，所以 $011 \operatorname{xor} 101 = 110$，即 $6$。

:::

输入格式

输入以如下格式从标准输入读入：

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出满足条件的整数对 $(l, r)$ 的个数。

样例 1

输入

4
2 5 4 6

输出

5

样例 2

输入

9
0 0 0 0 0 0 0 0 0

输出

45

样例 3

输入

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

输出

37

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i$
• 输入均为整数

样例解释 1

显然，$(l, r) = (1, 1), (2, 2), (3, 3), (4, 4)$ 都满足条件。此外，当 $(l, r) = (1, 2)$ 时，$A_1 \operatorname{xor} A_2 = A_1 + A_2 = 7$，所以也满足条件。没有其他满足条件的组合，因此答案为 $5$。