Problem 3990 --区间异或

3990: 区间异或

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $217$ 正确数量 $137$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
小可可在五年级暑假开始学习编程,编程语言中有一种按位异或(xor)”的运算引
起了他的莫大兴趣。于是,他思考这样的一个问题:给一个长度为 n 的整数序列 A和整数k,如
何计算出满足下列两个条件的整数对 (l, r) 的数量。 11≤l≤r≤n2Al xor Al+1 xor … xor Ar =k 这里的 xor 就是按位异或(C C++语言中按位异或运算符为^),求 a xor b 的原理是:将 a b 转换为二进制,如果 ab 的二进制表示中对应位置不相同,则异
或结果的二进制表示中对应位置为 1,如果 ab 的二进制表示中对应位置相同,则异或
结果的二进制表示中对应位置为 0。例如:计算 10 xor 12,二进制表示 10 1010,二
进制表示 12 110010 xor 12 结果的二进制表示是 0110,即为 6
输入有三行:
第一行一个正整数 n,表示整数序列 A 的元素个数。
第二行有 n 个整数,第 i 个整数 Ai 表示整数序列 A 的第 i 个元素的值。
第三行是一个正整数k,
输出一行,包括一个正整数,表示满足条件的整数对 (l, r) 的数量。
4
2 5 3 3
7
2
对于 20%的数据满足:Ai = 0 (1≤ i ≤n)。
另有 30%的数据满足:1≤ n ≤ 5000。
对于 100%的数据满足:1≤ n ≤ 2000000≤ Ai ≤ 2^20

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

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$17 $ms] thisislike 1094785 2024-04-13 10:09:03
内存最少[$1784 $KB] Tom 960355 2023-04-29 10:08:55
第一AC AOJ大管家 832591 2022-04-02 14:42:04
第一挑战 AOJ大管家 832566 2022-04-02 14:16:43

赛题来源/所属竞赛 2022年大学生程序设计竞赛网络赛本专科组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1692 2021-2022-2学期<算法分析与设计> 期末考试热身赛 2022-05-16 00:00:00 请登录