fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(i,a,b) for(int i=a; i<=b; i++)
  3. #define per(i,b,a) for(int i=b; i>=a; i--)
  4. using namespace std;
  5.  
  6. const int maxn = 1e5 + 5 ;
  7. int n, k ;
  8. long long a[maxn] ;
  9. long long pxor[maxn] ;
  10. map<long long, int> mp ;
  11. map<long long, bool> chk ;
  12. long long getinv(long long mask)
  13. {
  14.     rep(i,0,k-1)
  15.     {
  16.             mask ^= (1<<i) ;
  17.     }
  18.     return mask ;
  19. }
  20. int main()
  21. {
  22.     ios::sync_with_stdio(false) ;
  23.     cin.tie(NULL) ;
  24.     cin >> n >> k ;
  25.     rep(i,0,n-1) cin >> a[i] ;
  26.     rep(i,0,n-1)
  27.     {
  28.         if(i)
  29.         pxor[i] = (pxor[i-1]^a[i]) ;
  30.         else pxor[i] = a[i] ;
  31.         mp[pxor[i]]++ ;
  32.         chk[pxor[i]] = false ;
  33.     }
  34.     long long ret = (n*1LL*(n+1))/2 ;
  35.  
  36.     for(map<long long, int>::iterator it = mp.begin() ; it!=mp.end() ; it++)
  37.     {
  38.         long long inv = getinv(it->first) ;
  39.        // cout << it->first << " " <<  inv << "\n" ;
  40.         if(chk[it->first] || chk[inv]) continue ;
  41.         int cnt = mp[inv] ;
  42.         if(cnt > it->second)
  43.         {
  44.             long long sub = cnt-1 ;
  45.             long long add = it->second+1 ;
  46.             ret -= ((sub*(sub-1))/2 + (add*(add-1))/2) ;
  47.             chk[inv] = true ;
  48.         }
  49.     }
  50.     cout << ret << "\n" ;
  51.     return 0 ;
  52. }
  53.  
Success #stdin #stdout 0s 16800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/vmH4pj
language:
C++14 (gcc 8.3)
created:
6 years 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!