fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int T;
  8.     if(!(cin >> T)) return 0;
  9.     while(T--){
  10.         int N;
  11.         cin >> N;
  12.         vector<uint32_t> A(N);
  13.         for(int i=0;i<N;i++) cin >> A[i];
  14.         unordered_map<uint32_t, int64> cnt;
  15.         cnt.reserve(N*2 + 10);
  16.         cnt.max_load_factor(0.7);
  17.  
  18.         uint32_t px = 0;
  19.         // count prefix XORs P[0]..P[N]
  20.         cnt[px]++; // P[0] = 0
  21.         for(int i=0;i<N;i++){
  22.             px ^= A[i];
  23.             cnt[px]++;
  24.         }
  25.  
  26.         // Total length sum: N*(N+1)*(N+2)/6
  27.         int64 n = N;
  28.         __int128 totalLen = (__int128)n * (n+1) * (n+2) / 6;
  29.  
  30.         __int128 Z = 0;       // sum of C(cnt_v,2)
  31.         __int128 C3sum = 0;   // sum of C(cnt_v,3)
  32.         for(auto &kv : cnt){
  33.             int64 k = kv.second;
  34.             if(k >= 2) Z += (__int128)k * (k-1) / 2;
  35.             if(k >= 3) C3sum += (__int128)k * (k-1) * (k-2) / 6;
  36.         }
  37.  
  38.         __int128 ans = totalLen - Z - C3sum;
  39.         // print ans
  40.         long long out = (long long)ans; // fits in 64-bit for N <= 1e6 (N^3/6 ~ 1.6e17 < 2^63)
  41.         cout << out << '\n';
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1eh917
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!