Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <array>
- #include <vector>
- #include <numeric>
- #include <random>
- #include <chrono>
- using namespace std;
- //#define int long long
- #pragma comment(linker,"/STACK:1000000000,1000000000")
- const long long INF = 1e9 + 7;
- const int MAXN = 1e6 + 5;
- const int N = 1e5 + 10;
- int n, k;
- struct vertex {
- int next[2] = {0, 0};
- } v[30 * MAXN];
- array<int, 30 * MAXN> cn;
- int root = 0, top = 1;
- inline void add(int x) {
- int cur = root;
- for (int i = 29; i >= 0; --i) {
- int b = bool(x & (1 << i));
- if (v[cur].next[b] == 0) {
- v[cur].next[b] = top++;
- }
- cur = v[cur].next[b];
- ++cn[cur];
- }
- }
- long long ans = 0;
- inline void find(int x) {
- int cur = 0;
- for (int i = 29; i >= 0; --i) {
- int b = bool(x & (1 << i));
- if (k & (1 << i)) {
- if (v[cur].next[1 - b] == 0) {
- return;
- }
- cur = v[cur].next[1 - b];
- } else {
- if (v[cur].next[1 - b] != 0) {
- ans += cn[v[cur].next[1 - b]];
- }
- if (v[cur].next[b] == 0) {
- return;
- }
- cur = v[cur].next[b];
- }
- }
- ans += cn[cur];
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- add(0);
- cin >> n >> k;
- int sum = 0;
- for (int i = 0; i < n; ++i) {
- int x;
- cin >> x;
- sum ^= x;
- find(sum);
- add(sum);
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment