fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11.  
  12. const int N = 3e7+5; // 30 * N
  13.  
  14. int n, k;
  15.  
  16. int trie[N][2], cnt[N], nodes = 1;
  17.  
  18. void insert(int x) {
  19.     int u = 1;
  20.     for (int i = 29; i >= 0; i--) {
  21.         int b = (x >> i) & 1;
  22.         if (!trie[u][b]) trie[u][b] = ++nodes;
  23.         u = trie[u][b];
  24.         cnt[u]++;
  25.     }
  26. }
  27.  
  28. ll query(int p, int k) {
  29.     int u = 1;
  30.     ll res = 0;
  31.     for (int i = 29; i >= 0; i--) {
  32.         if (!u) break;
  33.         int b_p = (p >> i) & 1, b_k = (k >> i) & 1;
  34.         if (b_k == 1) u = trie[u][b_p ^ 1];
  35.         else {
  36.             if (trie[u][b_p ^ 1]) res += cnt[trie[u][b_p ^ 1]];
  37.             u = trie[u][b_p];
  38.         }
  39.     }
  40.     if (u) res += cnt[u];
  41.     return res;
  42. }
  43.  
  44. void solve() {
  45.     cin >> n >> k;
  46.     insert(0); // P_0 = 0
  47.     ll ans = 0;
  48.     int sum = 0;
  49.     for (int i = 0; i < n; i++) {
  50.         int x; cin >> x;
  51.         sum ^= x;
  52.         ans += query(sum, k);
  53.         insert(sum);
  54.     }
  55.     cout << ans << '\n';
  56. }
  57.  
  58. int main() {
  59.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  60.  
  61.     #define TASK "BAI4"
  62.     if (fopen(TASK".INP", "r")) {
  63.         freopen(TASK".INP", "r", stdin);
  64.         freopen(TASK".OUT", "w", stdout);
  65.     }
  66.  
  67.     int tests = 1; // cin >> tests;
  68.     while (tests--) solve();
  69.  
  70.     #ifdef LOCAL
  71.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  72.     #endif
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 1
1 2 3
stdout
copy 
5
https://ideone.com/ZGlzIp
language:
C++14 (gcc 8.3)
created:
4 hours 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!