Salvens

F

Aug 11th, 2023
984
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. //#define int long long
  13. #pragma comment(linker,"/STACK:1000000000,1000000000")
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 1e6 + 5;
  17. const int N = 1e5 + 10;
  18.  
  19. int n, k;
  20.  
  21. struct vertex {
  22.     int next[2] = {0, 0};
  23. } v[30 * MAXN];
  24.  
  25. array<int, 30 * MAXN> cn;
  26.  
  27. int root = 0, top = 1;
  28.  
  29. inline void add(int x) {
  30.     int cur = root;
  31.     for (int i = 29; i >= 0; --i) {
  32.         int b = bool(x & (1 << i));
  33.         if (v[cur].next[b] == 0) {
  34.             v[cur].next[b] = top++;
  35.         }
  36.         cur = v[cur].next[b];
  37.         ++cn[cur];
  38.     }
  39. }
  40.  
  41. long long ans = 0;
  42.  
  43. inline void find(int x) {
  44.     int cur = 0;
  45.     for (int i = 29; i >= 0; --i) {
  46.         int b = bool(x & (1 << i));
  47.         if (k & (1 << i)) {
  48.             if (v[cur].next[1 - b] == 0) {
  49.                 return;
  50.             }
  51.             cur = v[cur].next[1 - b];
  52.         } else {
  53.             if (v[cur].next[1 - b] != 0) {
  54.                 ans += cn[v[cur].next[1 - b]];
  55.             }
  56.             if (v[cur].next[b] == 0) {
  57.                 return;
  58.             }
  59.             cur = v[cur].next[b];
  60.         }
  61.     }
  62.     ans += cn[cur];
  63. }
  64.  
  65. signed main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.     cout.tie(nullptr);
  69.  
  70.     add(0);
  71.  
  72.     cin >> n >> k;
  73.     int sum = 0;
  74.     for (int i = 0; i < n; ++i) {
  75.         int x;
  76.         cin >> x;
  77.         sum ^= x;
  78.         find(sum);
  79.         add(sum);
  80.     }
  81.     cout << ans << '\n';
  82. }
Advertisement
Add Comment
Please, Sign In to add comment