Problem 3743 --2021-3-异或和(xorsum)

3743: 2021-3-异或和(xorsum)

上一题 正确率: $INF\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

小可可在五年级暑假开始学习编程，编程语言中有一种“按位异或(xor)”的运算引起了他的莫大兴趣。于是，他思考这样的一个问题：给一个长度为 n 的整数序列 A，如何计算出满足下列两个条件的整数对 (l, r) 的数量。
1、 1≤l≤r≤n；
2、 Al xor Al+1 xor … xor Ar = Al + Al+1 + … + Ar
这里的 xor 就是按位异或（C 或 C++语言中“按位异或”运算符为^），求 a xor b 的原理是：将 a 和 b 转换为二进制，如果 a、b 的二进制表示中对应位置不相同，则异或结果的二进制表示中对应位置为 1，如果 a、b 的二进制表示中对应位置相同，则异或结果的二进制表示中对应位置为 0。例如：计算 10 xor 12，二进制表示 10 是 1010，二进制表示 12 是 1100，10 xor 12 结果的二进制表示是 0110，即为 6。具体为下式：

小可可虽然提出了问题，但他自己不会解决，只好又要麻烦你解决啦.

Input

输入有两行：
第一行一个正整数 n，表示整数序列 A 的元素个数。
第二行有 n 个整数，第 i 个整数 Ai 表示整数序列 A 的第 i 个元素的值。

Output

输出一行，包括一个正整数，表示满足条件的整数对 (l, r) 的数量。

Sample Input复制

4 
2 5 4 6

Sample Output复制

5

提示

样例1解释：
(l, r) = (1, 1)、(2, 2)、(3, 3)、(4, 4)显然满足条件，还有(l, r) = (1, 2)也满足条件，因为 A1 xor A2=2 xor 5=7，而 A1 + A2=2 + 5=7。所以满足条件的整数对 (l, r) 的数量为 5。
对于 20%的数据满足：Ai = 0 (1≤ i ≤n)。另有 30%的数据满足：1≤ n ≤ 5000。
对于 100%的数据满足：1≤ n ≤ 200000，0≤ Ai ≤ 2^20。

推荐代码 查看3743 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$26 $ms] thisislike 1104177 2024-09-24 09:51:19
内存最少[$3156 $KB] thisislike 1104177 2024-09-24 09:51:19
第一AC thisislike 1104177 2024-09-24 09:51:19
第一挑战 thisislike 1104177 2024-09-24 09:51:19

赛题来源/所属竞赛 SS:省信息学小学组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛