← 返回题目列表

AtCoder · arc098_b

D. 异或和 2

中文机器翻译题面 查看原题

分数: 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