如何统计给定数组中异或和为偶数的连续子数组数量
异或和为偶数的连续子数组计数优化实现
核心推导逻辑
- 异或结果的奇偶性仅由参与运算数字的二进制最低位决定,高位运算不会改变结果的奇偶性:偶数最低位为0,奇数最低位为1
- 连续子数组的异或结果为偶数的充要条件可通过前缀异或性质推导:
定义
pre[i]为数组前i个元素的前缀异或值(约定pre[0]=0,代表空数组的异或和),则下标从l到r的连续子数组异或值等价于pre[r] ^ pre[l-1]
两个数异或结果为偶数,当且仅当二者奇偶性完全一致:奇偶性相同则异或后最低位为0,结果为偶数;奇偶性不同则最低位为1,结果为奇数
线性复杂度实现方案
不需要完整记录所有前缀异或值,仅通过两个计数变量即可完成统计:
- 维护两个计数器:
cnt0:遍历过程中已出现的、值为偶数的前缀异或的数量,初始值为1(对应约定的pre[0]=0)cnt1:遍历过程中已出现的、值为奇数的前缀异或的数量,初始值为0
- 遍历数组时仅跟踪当前前缀异或的奇偶性(无需计算完整异或值):
- 若当前前缀为偶数,将当前
cnt0的数值累加到结果中(每一个历史出现的偶数前缀,和当前前缀配对即可生成一个异或和为偶数的子数组),随后将cnt0自增1 - 若当前前缀为奇数,将当前
cnt1的数值累加到结果中,随后将cnt1自增1
- 若当前前缀为偶数,将当前
优化后的代码实现
t = int(input()) for _ in range(t): n = int(input()) arr = list(map(int, input().split())) cnt0 = 1 cnt1 = 0 cur_parity = 0 # 记录当前前缀异或的奇偶性,0为偶,1为奇 res = 0 for num in arr: # 仅提取当前数字的最低位参与奇偶性计算 cur_parity ^= (num & 1) if cur_parity == 0: res += cnt0 cnt0 += 1 else: res += cnt1 cnt1 += 1 print(res)
方案对比
- 原朴素解法采用两层嵌套循环遍历所有子数组,时间复杂度为O(n²),在数组规模较大时会出现运行超时
- 优化方案为单次线性遍历,时间复杂度O(n),空间复杂度O(1),无额外内存开销,可支持最大数组规模下的实时计算
内容的提问来源于stack exchange,提问作者beast_skas
相关产品推荐
相关产品推荐

