Codeforces Round #841 (Div. 2) C. Even Subarrays题意思路AC代码

101 阅读 0 评论 67 点赞

我是靠谱客的博主平常奇迹，这篇文章主要介绍Codeforces Round #841 (Div. 2) C. Even Subarrays题意思路AC代码，现在分享给大家，希望可以做个参考。

文章目录

题意
思路
AC代码

C. Even Subarrays
严格鸽题解
多向大佬学习

题意

题意：给我们一个数组a问我们有几个子区间的异或和满足因子个数是偶数。

思路

思路：首先因子的话都是成对出现的，那什么情况下是奇数呢，就是这个数是平方数的时候，那么此时因子有一对两个数是相同的，所以就肯定是奇数。

因次我们现在的目的就要找子区间异或和等于平方数的个数，然后用总的减去异或和等于平方数的子区间的个数即可。

首先我们看一下前缀和异或和 $p re [i] = a [1] ⨁ a [2] ⨁ a [3] ... a [i]$ 然后呢，我们想求一个区间的异或和也就是 $a [L] ⨁ a [L + 2] ⨁ a [L + 3] ... a [R]$ 那么这个区间异或怎么求呢，我们可以同过异或运算的性质来求 $x ⨁ 0 = x x ⨁ x = 0$ 也就是 $p re [R] - p re [L - 1] = (a [1] ⨁ a [2] ⨁ a [3] ... a [L - 1]) ⨁ a [L + 1] ⨁ a [L + 2] ... a [R] ⨁ (a [1] ⨁ a [2] ⨁ a [3] ... a [L - 1])$ 那么此时的前面的小括号里的部分和后面的小括号部分就抵消了，整个式子就等于 $a [L] ⨁ a [L + 2] ⨁ a [L + 3] ... a [R]$

然后我们得到上面的结论之后我们就可以枚举 $p re [R]$ 看有几个 $p re [R] ⨁ p re [L - 1] = n u m$ 这里的num为平方数上个式子也可以写成 $p re [L - 1] = p re [R] ⨁ n u m$ 。然后我们计一下个数最后用总的减去即可。
注意 $L - 1$ 是可以等于0的所以我们mp[0]初始值赋成1

AC代码

复制代码

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
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int mp[N], a[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
mp[0] = 1;
int ans = 0, pre = 0;
for (int i = 1; i <= n; i++)
{
pre ^= a[i];
for (int x = 0; x * x <= 2 * n; x++)
{
int num = x * x;
ans += mp[pre ^ num];
}
mp[pre]++;
}
cout << n * (n + 1) / 2 - ans << endl;
// memset(mp, 0, sizeof mp);
for (int i = 0; i < 2 * n; i++)
mp[i] = 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}