Codeforces Round 841 (Div. 2) C. Even Subarrays

题目

思路：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e9, maxm = 4e4 + 5;
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int N = 2e5;
// int a[505][5005];
// bool vis[505][505];
// char s[505][505];
int a[maxn], b[maxn];
int vis[maxn];
string s;
int n, m;struct Node{int val, id;bool operator<(const Node &u)const{return val < u.val;}
};
// Node c[maxn];// int ans[maxn], pre[maxn];int cnt[maxn];bool issq(int x){int sq = sqrt(x);return sq * sq == x;
}
//long long ? maxn ?
void solve(){int res = 0;int q, k;int x;cin >> n;int mx = 0;for(int i = 1; i <= n; i++){cin >> a[i];mx = max(mx, a[i]);}mx = (1LL << (__lg(mx) + 1)) - 1;int sq = sqrt(mx);// m = sq;int sum = 0;int Xor = 0;res = n * (n - 1) / 2 + n;for(int j = 0; j <= sq; j++){int val = j * j;for(int i = 0; i <= mx; i++){cnt[i] = 0;}cnt[0] = 1;//不选前缀也是一种选法Xor = 0;//每次都得置0for(int i = 1; i <= n; i++){//求异或和为某个数的子区间个数，求法跟两数之和为某个数的求法一样Xor ^= a[i];sum += cnt[val ^ Xor];// cout << val << ' ' << (val ^ Xor) << ' ' << cnt[val ^ Xor] << '\n';cnt[Xor]++;}}res -= sum;cout << res << '\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);// for(int i = 1; i <= N; i++){//     for(int j = i; j <= N; j += i){//         d[j]++;//     }// }// int cnt = 0;// for(int i = 1; i <= N; i++){//     if(d[i] % 2 == 0){//         cnt++;//     }//     else{//         cout << i << ' ';//     }// }// cout << cnt << '\n';int T = 1;cin >> T;while (T--){solve();}return 0;
}