你的原代码通过双重循环枚举所有子数组，再统计每个子数组的奇数个数，时间复杂度是O(n²)，当数组长度较大时很容易超时。我们可以通过挖掘XOR运算的奇偶性规律，结合前缀统计的思想，把解法优化到线性时间。

关键规律分析 #

首先要明确：子数组的XOR结果为偶数，等价于子数组中奇数的个数是偶数（包括0个）。原因是：

• 偶数的二进制最低位是0，奇数是1；XOR运算的最低位结果等于所有元素最低位的XOR结果。
• 多个1的XOR结果为0（即偶数）的条件是：1的个数是偶数（偶数个奇数XOR后最低位为0，整体结果为偶数）。

所以问题可以转化为：统计数组中奇数个数为偶数的子数组数量。

O(n)解法思路 #

我们可以用前缀计数的思想来快速计算：

1. 维护current_odd：记录从数组开头到当前位置的奇数总个数。
2. 维护两个计数器：
   • even_count：记录前缀中奇数个数为偶数的次数（初始值为1，因为前0个元素的奇数个数是0，属于偶数情况）
   • odd_count：记录前缀中奇数个数为奇数的次数
3. 遍历数组时，每遇到一个奇数就更新current_odd，然后根据current_odd的奇偶性更新对应的计数器。
4. 最终符合条件的子数组数量 = 从所有偶数前缀中选2个的组合数 + 从所有奇数前缀中选2个的组合数。这是因为：
   • 若两个前缀的奇数个数奇偶性相同，它们之间的子数组的奇数个数就是偶数，对应的XOR结果为偶数。

优化后的代码 #

l = list(map(int, input().split()))
current_odd = 0
even_count = 1  # 初始状态：前0个元素的奇数个数为0（偶数）
odd_count = 0

for num in l:
    if num % 2 != 0:
        current_odd += 1
    # 更新对应计数器
    if current_odd % 2 == 0:
        even_count += 1
    else:
        odd_count += 1

# 计算组合数：C(n,2) = n*(n-1)//2
result = even_count * (even_count - 1) // 2 + odd_count * (odd_count - 1) // 2
print(result)

验证示例 #

对于输入[1,2,3,4]：

• 遍历过程中current_odd依次变为1、1、2、3
• even_count最终为2（初始1 + 遍历到第3个元素时加1）
• odd_count最终为3（遍历到第1、2、4个元素时各加1）
• 计算结果：2*1//2 + 3*2//2 = 1 + 3 = 4，和示例答案一致。

这个解法只需要遍历数组一次，时间复杂度为O(n)，空间复杂度为O(1)，完全符合你的要求。

内容的提问来源于stack exchange，提问作者Oliver Queen