异或和为 k 的子数组个数
P5522. 异或和为 k 的子数组个数
场次:2026年10月22日-AI方向 · 来源:CodeFun2000 P5522
题目描述
给定一个长度为 的非负整数数组 和一个非负整数 ,请求出有多少个连续子数组的异或和恰好等于 。
子数组指一段连续的元素 (),它的异或和是这些元素逐个异或的结果;长度为零的空段不算子数组。
输入格式
第一行输入两个整数 (,)。
第二行输入 个非负整数 ()。
输出格式
输出一个整数,表示异或和等于 的连续子数组个数。
示例
示例 1
输入:
5 6
8 0 6 7 3输出:
2解题思路
判定标准:一段区间的异或,等于两个前缀异或的一次相消
最直接的做法是枚举左右端点,边扫边异或:
ans = 0
for l in range(n):
cur = 0
for r in range(l, n): # 固定左端点,右端点一路右移
cur ^= a[r]
ans += cur == k这段代码没错,但端点对是 个。要让「一段区间的异或和」变成一个 就能读出来的量,靠的是异或的相消性 。定义前缀异或
那么
理由只有一句: 是「」与「」的异或,再异或一次 (也就是那段 ),前一半两两抵消,剩下正好是区间。
于是题目换了个说法,而这句话正是全题的判定标准:
数一数有多少对下标 ,满足 且 。
对应「子数组非空」, 对应「从 开始」。前缀不必真的开一个数组,边扫边算就行:
pref = 0
for x in a: # 循环一轮,pref 就是 pref[j];上一轮的 pref 就是 pref[j-1]
pref ^= x为什么是哈希计数:查的是「值相等」,不是「范围」
对上面的等式做一次移项。异或的逆运算还是异或,两边同异或 得
扫到 时, 是一个确定的数字,问题变成:「在 这段历史里,这个值出现过几次?」这类查询的键是值,于是哈希表存「值 → 出现次数」,查询 ,整题 。
这也是唯一的一条路,另一条常见思路在这里不成立:
- 滑动窗口不行。窗口和只有在元素全为正时才随右端点单调,收缩才有依据;异或没有大小关系,前缀异或也不单调,「窗口该往左挪还是往右扩」没有判据。
- 排序 / 二分也不行。要找的是「某个精确值出现过几次」,不是「范围内有多少个」。
题面把 定在 , 枚举是 个端点对,必定超时; 的哈希计数才是对上这一档数据的写法。核心代码只有这么几行:
def count_xor_subarrays(nums, k):
count = {0: 1} # 值 -> 出现次数,先把空前缀记进去
pref = 0
ans = 0
for x in nums:
pref ^= x
ans += count.get(pref ^ k, 0) # 有多少个历史前缀能和当前前缀拼出 k
count[pref] = count.get(pref, 0) + 1
return ans两处细节:种子 {0: 1} 与「先查后记」
种子。 哈希表一开始就放着 0 -> 1,它代表 这个空前缀。没有它,任何「从 开始」的子数组都数不到——它们的左端点正是 。拿 、 试一下:扫到 时 ,需要的历史值是 ,而表里唯一的 就是这颗种子。官方样例的两次命中都落在 的区间上,缺了种子它照样输出 ,所以这一条只有自己造用例才会显形。
顺序。 循环里先 ans +=、再 count[pref] += 1,两步不能换。换过来时,当前前缀先登记进表,紧接着查的 pref ^ k 在 的情况下恰好等于 pref 自己,于是「 的空区间」被算成一个子数组——而它根本不是子数组。 时 pref ^ k != pref,这个顺序错误不显形,所以它只在 的用例上爆炸(官方样例 就碰不到)。
顺带一提,表里存的是次数而不是下标列表:同一个前缀值在不同位置出现,每个位置都是一个不同的左端点,都要各算一次(、 时前缀 在三个位置出现,贡献 )。存下标列表虽然也能做对,但空间会退化,而且没有额外信息。
完整代码实现
import sys
def count_xor_subarrays(nums, k):
"""统计异或和恰好等于 k 的连续子数组个数。"""
# count[x] = 在当前位置之前,前缀异或等于 x 的次数
# 空前缀(一个数都没取)的异或为 0,先记 1 次
count = {0: 1}
pref = 0
ans = 0
for x in nums:
pref ^= x # 走到 x 为止的前缀异或
ans += count.get(pref ^ k, 0) # 需要的历史前缀是 pref ^ k
count[pref] = count.get(pref, 0) + 1
return ans
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
k = int(data[1])
nums = [int(x) for x in data[2:2 + n]]
print(count_xor_subarrays(nums, k))
if __name__ == "__main__":
solve()示例推演
示例 1:,
前缀异或序列是 (下标 到 )。表初始为 。
| 轮次 | 读入 | 要找的 | 表中命中 | 累计答案 | 表(值→次数) | |
|---|---|---|---|---|---|---|
| 1 | 8 | 8 | 0 次 | 0 | ||
| 2 | 0 | 8 | 0 次 | 0 | ||
| 3 | 6 | 14 | 2 次 | 2 | ||
| 4 | 7 | 9 | 0 次 | 2 | ||
| 5 | 3 | 10 | 0 次 | 2 |
第 3 轮一次拿到 2 次命中:8 在前缀里出现过两次( 与 ),它们都能和 拼出一段异或为 的区间:
- 命中 ,对应 ,即 ,异或为 ;
- 命中 ,对应 ,即 ,异或为 。
第 4、5 轮要找的 与 在表里都没出现过,答案停在 。手工枚举也对得上:以 开头的五段异或是 ,以 开头的四段是 ,以 开头的三段是 ,以 开头的两段是 ,最后一段是 ——只有 与 等于 。
再看一组:,
官方样例只有一组,而「种子」与「先查后记」这两处细节都要在 时才看得出来,所以单独走一遍。
| 轮次 | 读入 | 要找的 | 表中命中 | 累计答案 | 表(值→次数) | |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 次 | 1 | ||
| 2 | 0 | 0 | 2 次 | 3 |
第 1 轮命中 (区间 );第 2 轮命中 与 (区间 与 )。三段全部命中,答案 。
第 1 轮那 次命中完全来自种子 ,没有种子这一步就是 ;而每轮「先查后记」,才让第 2 轮看到的候选只剩前两轮登记过的前缀,不会把当前位置自己算进左端点。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举左右端点、边扫边异或 | 正确,但端点对本身就是 个,规模一大就超时 | ||
| 前缀异或 + 哈希计数(最优) | 每个元素一次异或、一次查表、一次更新,都是 ;表里最多 个不同的前缀值 |
空间上不需要 的前缀数组:pref 只保留当前值,历史信息全在哈希表里。答案最大可以到 (全 数组、 时每段都命中),Python 的整数没有溢出问题;前缀异或也不会越算越大——异或只按位操作、不进位,结果的位宽不超过两个操作数中较长的那一个。
易错点总结
1. 忘了种子 {0: 1}
count = {} 起手时,、 会输出 而不是 ——少掉的恰好是 [1,2]:它需要的历史前缀是 ,而空前缀从来不进表。现象很统一:所有从 开始的子数组全部丢失,答案只会偏小、不会偏大。
2. 先登记当前前缀、再去查表
把 count[pref] += 1 挪到 ans += 之前, 时结果不变, 时每个位置都会多算一次「 的空区间」:、 会输出 而不是 (第一轮查到 次、第二轮查到 次)。这类错误在随机测试里很容易漏掉,因为只有 时才显形。
3. 把「出现次数」写成「是否出现过」
写成 if pref ^ k in count: ans += 1 时,值相同但位置不同的前缀只被算一次。、 时正确答案是 (三段单元素 + 两段两元素 + 一段三元素),这种写法只给出 ——每个位置各贡献 。判定标准是「有多少个左端点」,所以表里必须是计数。