题意

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

思路

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

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

首先我们看一下前缀和异或和$$pre[i]=a[1]⨁a[2]⨁a[3]...a[i]$$然后呢，我们想求一个区间的异或和也就是$$a[L]⨁a[L+2]⨁a[L+3]...a[R]$$那么这个区间异或怎么求呢，我们可以同过异或运算的性质来求$$x⨁0=xx⨁x=0$$也就是$$pre[R]-pre[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]$$

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

AC代码

#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;
}

最后

以上就是平常奇迹为你收集整理的Codeforces Round #841 (Div. 2) C. Even Subarrays题意思路AC代码的全部内容，希望文章能够帮你解决Codeforces Round #841 (Div. 2) C. Even Subarrays题意思路AC代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。