#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。