C. Even Subarrays

原题链接

题解

这题用到的知识点很多， 思维+前缀异或+容斥原理。

1、题目告诉我们要找 被除数个数 是偶数个的异或和，那么什么数的 被除数 有偶数个？

答案：非完全平方数。

2、非完全平方数太多了，不好求。而我们又知道 所有序列 个数为（n+1）*n/2 所以我们只要求出序列异或和为完全平方数的个数即可。

注意，由于异或的性质，n个 <=n 的数异或结果 <=2n。所以我们要遍历2n以内的所有完全平方数。

3、前缀异或的应用：我们创建一个异或前缀和数组，再统计每个前缀的值的出现次数。  然后枚举右端点，接着枚举  ≤ 2n 的完全平方数，由异或前缀和数组可以得到符合条件的左端点个数，累加即可。

code 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N],n,xor_a[N];

void solve(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        xor_a[i]=xor_a[i-1]^a[i];
    }
    
    int vis[n<<1+5];
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    
    int up=sqrt(n<<1);
    ll sum=(ll(n)+1ll)*ll(n)/2ll;
    for (int i=1;i<=n;i++){
        for (int j=0;j<=up;j++){
            sum-=ll(vis[(j*j)^xor_a[i]]);
        }
        vis[xor_a[i]]++;
    }
    
    cout<<sum<<endl;
}

int main(){
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}