题目描述：
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
- 选择两个满足
0 <= i, j < nums.length 的不同下标 i 和 j 。 - 选择一个非负整数
k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。 - 将
nums[i] 和 nums[j] 都减去 2k 。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
数据范围：
$1\le nums.len \le 10^5, 0\le nums[i] \le 10^6$
题解：
每次选两个都减去 $2^k$ ，说明 $2^k$ 应该是偶数个，即每一位上都应该是偶数个的。直接使用异或前缀和，如果一个区间的异或前缀和为 $0$ ，说明是合法区间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
long long beautifulSubarrays(vector<int> &nums)
{
unordered_map<int, int> mp;
mp[0] = 1;
long long ans = 0;
int sum = 0;
for (auto &x : nums)
{
sum ^= x;
if (mp.count(sum))
ans += mp[sum];
mp[sum]++;
}
return ans;
}
};
|