主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem F: 异或和(xorsum)
上一题
正确率: $24.62\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$128$ 兆字节/Megabyte(s)
提交总数
$130$
正确数量
$32$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
递推
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
递推
单击选择分类:
Description
<div> <span style="font-size:16px;">小可可在五年级暑假开始学习编程,编程语言中有一种“按位异或(xor)”的运算引</span> </div> <div> <span style="font-size:16px;">起了他的莫大兴趣。于是,他思考这样的一个问题:给一个长度为 n 的整数序列 A,如</span> </div> <div> <span style="font-size:16px;">何计算出满足下列两个条件的整数对 (l, r) 的数量。</span> </div> <div> <span style="font-size:16px;">1、1≤l≤r≤n;</span> </div> <div> <span style="font-size:16px;">2、Al xor Al+1 xor … xor Ar = Al + Al+1 + … + Ar</span> </div> <div> <span style="font-size:16px;">这里的 xor 就是按位异或(C 或 C++语言中“按位异或”运算符为^),求 a xor b</span> </div> <div> <span style="font-size:16px;">的原理是:将 a 和 b 转换为二进制,如果 a、b 的二进制表示中对应位置不相同,则异</span> </div> <div> <span style="font-size:16px;">或结果的二进制表示中对应位置为 1,如果 a、b 的二进制表示中对应位置相同,则异或</span> </div> <div> <span style="font-size:16px;">结果的二进制表示中对应位置为 0。例如:计算 10 xor 12,二进制表示 10 是 1010,二</span> </div> <p> <span style="font-size:16px;">进制表示 12 是 1100,10 xor 12 结果的二进制表示是 0110,即为 6。</span> </p> <p> <span style="font-size:16px;"> </span> </p> <div> 小可可虽然提出了问题,但他自己不会解决,只好又要麻烦你解决啦。 </div> <br /> <p> <br /> </p>
Input
<div> <span style="font-size:16px;">输入有两行:</span> </div> <div> <span style="font-size:16px;">第一行一个正整数 n,表示整数序列 A 的元素个数。</span> </div> <p> <span style="font-size:16px;">第二行有 n 个整数,第 i 个整数 Ai 表示整数序列 A 的第 i 个元素的值。</span> </p> <p> <span style="font-size:16px;"> </span> </p> <div> 【数据范围】 </div> <div> 对于 20%的数据满足:Ai = 0 (1≤ i ≤n)。 </div> <div> 另有 30%的数据满足:1≤ n ≤ 5000。 </div> <div> 对于 100%的数据满足:1≤ n ≤ 200000,0≤ Ai ≤ 2 <sup>20</sup>。 </div> <br /> <p> <br /> </p>
Output
<div> <span style="font-size:16px;">输出一行,包括一个正整数,表示满足条件的整数对 (l, r) 的数量。</span> </div>
Sample Input
复制
4 2 5 4 6
Sample Output
复制
5
提示
<div> <span style="font-size:16px;">【样例 解释】</span> </div> <div> <span style="font-size:16px;">(l, r) = (1, 1)、(2, 2)、(3, 3)、(4, 4)显然满足条件,还有(l, r) = (1, 2)也满足条件,因</span> </div> <div> <span style="font-size:16px;">为 A1 xor A2=2 xor 5=7,而 A1 + A2=2 + 5=7。所以满足条件的整数对 (l, r) 的数量为 5。</span> </div>
AOJ
Please Login