You need to enable JavaScript to run this app. 如何统计给定数组中异或和为偶数的连续子数组数量
优惠活动
大模型
产品
解决方案
定价
更多

如何统计给定数组中异或和为偶数的连续子数组数量

异或和为偶数的连续子数组计数优化实现

核心推导逻辑

  • 异或结果的奇偶性仅由参与运算数字的二进制最低位决定,高位运算不会改变结果的奇偶性:偶数最低位为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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.08 00:36:00