fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4.  
  5. int64 zeroXorSegments(vector<int64>& data) {
  6.     unordered_map<int64, int64> freq;
  7.     int64 prefix = 0, zeroCount = 0;
  8.     freq[0] = 1;
  9.  
  10.     for (auto num : data) {
  11.         prefix ^= num;
  12.         if (freq.count(prefix)) zeroCount += freq[prefix];
  13.         freq[prefix]++;
  14.     }
  15.  
  16.     return zeroCount;
  17. }
  18.  
  19. int main() {
  20.     ios::sync_with_stdio(false);
  21.     cin.tie(nullptr);
  22.  
  23.     int64 testCases;
  24.     cin >> testCases;
  25.  
  26.     while (testCases--) {
  27.         int64 len;
  28.         cin >> len;
  29.         vector<int64> seq(len);
  30.         for (int64 i = 0; i < len; i++) cin >> seq[i];
  31.  
  32.         vector<int64> prefixXor(len + 1, 0);
  33.         for (int64 i = 1; i <= len; i++)
  34.             prefixXor[i] = prefixXor[i - 1] ^ seq[i - 1];
  35.  
  36.         vector<int64> leftZero(len + 1, 0);
  37.         for (int64 i = 1; i <= len; i++) {
  38.             int64 localCount = 0;
  39.             for (int64 start = 1; start <= i; start++) {
  40.                 if ((prefixXor[i] ^ prefixXor[start - 1]) == 0)
  41.                     localCount++;
  42.             }
  43.             leftZero[i] = localCount;
  44.         }
  45.  
  46.         vector<int64> rightZero(len + 2, 0);
  47.         for (int64 i = 1; i <= len; i++) {
  48.             int64 localCount = 0;
  49.             for (int64 end = i; end <= len; end++) {
  50.                 if ((prefixXor[end] ^ prefixXor[i - 1]) == 0)
  51.                     localCount++;
  52.             }
  53.             rightZero[i] = localCount;
  54.         }
  55.  
  56.         int64 invalidTriplets = 0;
  57.         for (int64 i = 1; i < len; i++)
  58.             invalidTriplets += leftZero[i] * rightZero[i + 1];
  59.  
  60.         invalidTriplets += zeroXorSegments(seq);
  61.  
  62.         int64 allTriplets = (len * (len + 1) * (len + 2)) / 6;
  63.         int64 validTriplets = allTriplets - invalidTriplets;
  64.  
  65.         cout << validTriplets << "\n";
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
4
2
0 0
3
1 1 1
3
1 2 3
7
0 1 0 2 0 3 0
stdout 
0
8
9
72
https://ideone.com/gIxqh0
language:
C++14 (gcc 8.3)
created:
6 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!