分数: 500 点
问题陈述
有一个整数序列 A 长度 N.
查找整数对的数量 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 为 X。在二进制表示中 X,中的数字 2^k的地点 (0 \leq k; k 是一个整数)是 1 如果其中有奇数个整数 c_1, c_2, ...c_m 其二进制表示有 1 在 2^k的地点,以及 0 如果该数字是偶数。
例如,让我们计算 XOR 3 和 5。的二进制表示 3 is 011,以及二进制表示 5 is 101,因此 XOR 具有二进制表示形式 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