fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. // Function to solve a single test case
  9. long long solve() {
  10.     int N;
  11.     cin >> N;
  12.     vector<long long> A(N);
  13.  
  14.     // Use a map to store frequencies of prefix XOR sums
  15.     // Key: prefix XOR sum, Value: count
  16.     map<long long, long long> counts;
  17.  
  18.     long long current_xor_sum = 0;
  19.  
  20.     // S[0] is 0. Add it to the count.
  21.     counts[0] = 1; 
  22.  
  23.     for (int i = 0; i < N; ++i) {
  24.         cin >> A[i];
  25.         current_xor_sum ^= A[i];
  26.         // S[i+1] is current_xor_sum
  27.         counts[current_xor_sum]++;
  28.     }
  29.  
  30.     // 1. Calculate the total sum of all subarray lengths
  31.     // Use (long long) to prevent integer overflow during multiplication
  32.     long long n_ll = N;
  33.     long long total_length_sum = n_ll * (n_ll + 1) * (n_ll + 2) / 6;
  34.  
  35.     // 2. Calculate the total "discount" (SubtractionTerm)
  36.     long long subtraction_term = 0;
  37.  
  38.     // Iterate over all (value, p) pairs in our frequency map
  39.     for (auto const& [value, p] : counts) {
  40.         // If a value appears p >= 2 times, it contributes to the subtraction
  41.         if (p >= 2) {
  42.             // The contribution is (p-1) * p * (p+1) / 6, which is C(p+1, 3)
  43.             subtraction_term += (p - 1) * p * (p + 1) / 6;
  44.         }
  45.     }
  46.  
  47.     // 3. The final answer is the total sum minus the discount
  48.     return total_length_sum - subtraction_term;
  49. }
  50.  
  51. int main() {
  52.     int T;
  53.     cin >> T;
  54.     for (int i = 1; i <= T; ++i) {
  55.         long long result = solve();
  56.         cout << "Case #" << i << ": " << result << endl;
  57.     }
  58.     return 0;
  59. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4
2
0 0
3
1 1 1
3
1 2 3
7
0 1 0 2 0 3 0
stdout
copy 
Case #1: 0
Case #2: 8
Case #3: 9
Case #4: 72
https://ideone.com/sxvhQO
language:
C++ (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!