当前没有测试数据。

题目描述

给定一个长度为 N 的整数序列 A。

请你求出满足下述条件的整数对 l,r（1 ≤ l ≤ r ≤ N）的数量：

$$A_l\ \text{\(\text{xor}\)}\ A_{l+1}\ \text{\(\text{xor}\)}\ \dots\ \text{\(\text{xor}\)}\ A_r = A_l\ +\ A_{l+1}\ +\ \dots\ +\ A_r$$

其中 $\text{\(\text{xor}\)}$ 代表按位异或运算。

异或的定义

整数 $c_1,c_2,\dots,c_m$ 的异或定义如下：

设异或结果为 X。在 X 的二进制表示中，对于 $2^k$ 这一位（0 ≤ k，k 为整数）： 如果 $c_1,c_2,\dots,c_m$ 中有奇数个数的二进制在 $2^k$ 位上为 1，则 X 的这一位为 1；否则为 0。

例如，计算 3 和 5 的异或。3 的二进制是 011，5 的二进制是 101，因此异或结果的二进制为 110，也就是 6。

约束条件

• 1 ≤ N ≤ 2 × 10^5
• 0 ≤ A_i < 2^20
• 输入中的所有数值均为整数。

输入格式

从标准输入按如下格式读入数据：

$N$

$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出满足条件的整数对 l,r（1 ≤ l ≤ r ≤ N）的数量。

样例输入输出

4
2 5 4 6

5

(l,r)=(1,1),(2,2),(3,3),(4,4) 显然满足条件。(l,r)=(1,2) 同样满足，因为 A_1 (\text{xor}) A_2 = A_1 + A_2 = 7。不存在其他满足条件的数对，因此答案为 5。

9
0 0 0 0 0 0 0 0 0

45

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

37

原题链接

原题链接