djj的异或序列

题目介绍

有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$，求有多少个不同的区间 $[l, r],\ (l\leq r)$ ，满足 $a_l \operatorname{\,xor\,} a_{l + 1} \operatorname{\,xor\,} \cdots \operatorname{\,xor\,} a_r = 0$，其中 $\operatorname{\,xor\,}$ 表示按位异或运算。

特别地，如果 $l = r$，我们认为上面的计算结果是 $a_l$。

输入格式

输入共两行。

第一行为一个正整数 $n$，表示序列的长度。

接下来一行，有 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

输出格式

一行一个整数，表示符合题意的区间数量。

输入样例

5
1 2 3 2 1

输出样例

2

样例解释

只有两个区间 $[1,3]$ 和 $[3,5]$ 的异或值为 $0$：

• $[1,3]$：$1 \operatorname{\,xor\,} 2 \operatorname{\,xor\,} 3 = 0$；

• $[3,5]$：$3 \operatorname{\,xor\,} 2 \operatorname{\,xor\,} 1 = 0$。

数据范围

对于 $50\%$ 的数据，$1\leq n \leq 100$；

对于 $70\%$ 的数据，$1\leq n\leq 10,000$；

对于 $100\%$ 的数据，$1\leq n\leq 10^5$。

数据保证任何一个区间的异或值不会超过 $10^5$。

HINT

复习一下异或的运算性质：

• $a \operatorname{\,xor\,} a = 0$ ，即一个数异或其本身一定是 $0$；如果两个数异或值是 $0$，那么这两个数也一定相同；
• 异或运算满足交换律和结合律；

如果想要拿满分，需要将算法的时间复杂度优化为线性。