xor_fast.cpp

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

// Function to find number of subarrays such that
// XOR of one half is equal to the other
int findSubarrCnt(int arr[], int n)
{
    // Variable to store current XOR's
    int XOR = 0;

    // Array to store prefix XOR's
    int prefix[n];

    for (int i = 0; i < n; ++i) {

        // Calculate XOR until this index
        XOR = XOR ^ arr[i];

        // Store the XOR in prefix array
        prefix[i] = XOR;

    // cout<<"Prefix at "<<i<<" ="<<XOR<<endl;
    }
    
    //map to store prefix and vector of indices where these prefix are found in the array
    //The trick is if Xor of elements from i->j=0 then Prefix[i-1]==Prefix[j]
    unordered_map<int, vector<int>> group;
    
    //Push index of prefix 0 as -1 as starting prefix is 0
    group[0].push_back(-1);
    for (int i = 0; i < n; ++i)
            group[prefix[i]].push_back(i);

    int sum = 0;
    
    //iterating over all prefix in group
    for(auto x: group){
       //cout<<endl<<"Prefix = "<<x.first<<endl;

       vector<int> temp = x.second;

       int n = temp.size();

       //for(auto y:temp)
        //cout<<y<<" ";
      //
       //cout<<endl;
       
       //Calculating sum of differences of all pairs of indices i.e. sum of (length-1) of all subarrays for prefix x.first
       for (int i=n-1; i>=0 and n>1; i--){
       //cout<<temp[i]<<" "<<sum<<" ";
        sum = sum + i*temp[i] - (n-1-i)*temp[i]-i;
       }

        
        // cout<<"Sum="<<sum<<"\t"<<"Ans="<<ans<<endl;
    }

    return sum;
}

// Driver Code
int main()
{
   int T;
	int N;
	cin>>T;
	while(T--){
	    cin>>N;
	    int a[N],counterr=0;
	    for(int i=0;i<N;i++)
	        cin>>a[i];
        cout <<findSubarrCnt(a, N)<<endl;
	}
    return 0;
}