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、 A_l xor A_l+1 xor … xor A_r = A_l + A_l+1 + … + A_r
这里的 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复制

提示

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

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[ $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

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

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

Description

Input

Output

Sample Input复制

Sample Output复制

提示

推荐代码 查看3743 所有题解 var params = { subject: '视频播放', coin_amount:50, word:3743, goods_id: 31 }; 上传题解视频得图灵币

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

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