P14359 [CSP-J 2025] 异或和 / xor（官方数据）
错误思路
1. 暴力___概不多说，暴力出奇迹
直接枚举所有可能的子数组，计算每个子数组的异或和并判断是否等于k。但数组长度最大可达5×10⁵，枚举所有子数组的时间复杂度为O(n²)，会超时，无法通过大数据。
2. DP___结论，特殊性质和重要
尝试设计动态规划状态记录前i个元素中合法子数组的个数，但异或和的无后效性难以直接体现，状态转移方程难以设计，且无法高效处理“非重叠”要求，最终效果不佳。
发现
异或运算存在关键性质，是解题的核心：
- 当a^b=c时，可推导得出：
- a^c=b（用c异或等式两边，抵消b）
- b^c=a（用c异或等式两边，抵消a）
结合前缀异或和的定义（s[i] = a[1]a[2]…^a[i]），子数组[l, r]的异或和为s[r]^s[l-1]（异或的“抵消性”：相同元素异或结果为0）。因此，要找异或和为k的子数组[l, r]，等价于找s[l-1] = s[r]k（由s[r]s[l-1] = k推导而来）。
思考
基于上述性质，用前缀和+集合的思路解题：
- 维护一个集合st，记录已出现过的前缀异或和，用于快速查询是否存在s[l-1] = s[r]^k；
- 初始时集合加入s[0] = 0（空数组的异或和），适配子数组从第一个元素开始的情况；
- 遍历数组计算前缀和s[i]，若s[i]^k在集合中存在，说明找到合法子数组，答案加1；
- 由于要求子数组非重叠，找到合法子数组后需重置状态：将当前前缀和s[i]设为0（视为新数组起点），清空集合（重新记录新数组的前缀和）；
- 每次遍历后将当前前缀和加入集合，供后续元素查询。
代码
#include<bits/stdc++.h>
using namespace std;// 全局变量说明：
// st：存储已出现的前缀异或和，初始加入s[0]=0（空数组异或和）
// n：数组长度，k：目标异或和
// a[]：原始数组，s[]：前缀异或和数组
// ans：统计合法非重叠子数组个数
set<int> st = {0};
int n, k;
const int MAXN = 500005; // 适配题目n≤5×10^5的数据范围
int a[MAXN], s[MAXN], ans = 0;int main() {// 输入数组长度和目标异或和cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];// 计算前缀异或和：s[i] = 前i个元素的异或和s[i] = s[i - 1] ^ a[i];// 检查是否存在s[l-1] = s[i]^k，即是否有合法子数组[l, i]if (st.find(s[i] ^ k) != st.end()) {ans++; // 找到合法子数组，答案加1s[i] = 0; // 重置前缀和，视为新数组起点（保证非重叠）st.clear(); // 清空集合，重新记录新数组的前缀和}// 将当前前缀和加入集合，供后续元素查询st.insert(s[i]);}// 输出合法子数组个数cout << ans << '\n';return 0;
}
补充说明
- 时间复杂度：每个元素的插入和查询操作都是O(log m)（m为集合中元素个数，重置后m最多为当前子数组长度），整体时间复杂度接近O(n log n)，可高效处理5×10⁵规模的数据；
- 重置机制的必要性：若不重置，可能会找到包含已统计子数组的重叠区间，违反“非重叠”隐含要求（该逻辑是通过官方数据的关键）；
- 初始集合初始化：st={0}是为了处理“子数组从第一个元素开始”的情况，例如当s[i]=k时，s[i]^k=0，集合中存在0，即可统计该子数组。