← 返回题目列表

Codeforces · 1109/A

A. 萨莎和一点放松

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

Sasha 喜欢编程。有一次,在一场漫长的比赛中,萨沙觉得自己有点累,需要放松一下。所以他做到了。但由于萨沙不是一个普通人,所以他更喜欢异常放松。闲暇时,Sasha 喜欢解决未解决的问题,因为解决问题非常有用。

因此,Sasha 决定解决以下问题:

你有一个数组 $$$a$$$ ,其中包含 $$$n$$$ 整数。您需要计算有趣的对 $$$(l, r)$$$ $$$(l \leq r)$$$ 的数量。要检查 $$$(l, r)$$$ 是否是有趣的对,请取 $$$mid = \frac{l + r - 1}{2}$$$,然后如果 $$$r - l + 1$$$ 是偶数且 $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$$$,那么这对就很有趣了。换句话说,从$$$l$$$到$$$r$$$的子数组左半部分的元素$$$\oplus$$$应该等于右半部分的元素$$$\oplus$$$。请注意,$$$\oplus$$$ 表示按位异或运算。

是时候继续解决比赛了,所以莎莎要求你解决这个任务。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) — 数组本身。

输出

打印一个整数——有趣对的数量。您应该仅考虑 $$$r - l + 1$$$ 为偶数的对。

示例

输入 #1

5
1 2 3 4 5

输出 #1

1

输入 #2

6
3 2 2 3 7 6

输出 #2

3

输入 #3

3
42 4 2

输出 #3

0

注意

像Sasha一样酷,解决问题!

在第一个示例中,唯一有趣的对是 $$$(2, 5)$$$,如 $$$2 \oplus 3 = 4 \oplus 5 = 1$$$。

在第二个示例中,有趣的对是 $$$(2, 3)$$$、$$$(1, 4)$$$ 和 $$$(3, 6)$$$。

在第三个示例中,没有有趣的对。