#3781. 题目2-子数组异或和为 K 的个数-前缀异或和

题目2-子数组异或和为 K 的个数-前缀异或和

【题目描述】
给定一个长度为 n 的整数数组和整数 K,求数组中有多少个连续子数组的异或和恰好等于 K。

提示:若设 pre[i] 为前缀异或和,则任意子数组 [L, R] 的异或和为 pre[R] ^ pre[L-1]。利用这一性质结合哈希表,可将总体时间复杂度降低到 O(n)。

【输入格式】

  • 第一行包含两个正整数 n 和 K (1 ≤ n ≤ 10^5,0 ≤ K < 2^31)。
  • 第二行包含 n 个非负整数,表示数组元素。

【输出格式】

  • 输出一个整数,表示满足条件的连续子数组个数。

【样例输入】

5 4
4 2 2 6 4

【样例输出】

4

【说明】
例如,上述样例中满足条件的子数组包括:

  • [4](第 1 个元素),异或和为 4;
  • [4,2,2](第 1~3 个元素),异或和为 4;
  • [2,6](第 3~4 个元素),异或和为 4;
  • [4](第 5 个元素),异或和为 4。