CF - 665E 字典树

题意：

思路：

代码：

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;typedef long long ll;const int MAXN = 1e6 + 10;const int maxbit = 33;struct node {	node *Next[2];	ll cnt;};struct Trie {	node *root;	void init() {		root = new node;		root->Next[0] = root->Next[1] = NULL;	}	void ins(ll x) {		node *p = root;		for (int i = maxbit; i >= 0; i--) {			int id = (x & (1LL << i)) ? 1 : 0;			if (p->Next[id] == NULL) {				node *q = new node;				for (int j = 0; j < 2; j++) q->Next[j] = NULL;				p->Next[id] = q;				p = p->Next[id];				p->cnt = 1;			}			else {				p = p->Next[id];				p->cnt++;			}		}	}	ll dfs(node *p, ll x, ll k, int deep) {		if (p == NULL) return 0;		if (deep == -1) return p->cnt;		int bx = (x & (1LL << deep)) ? 1 : 0, bk = (k & (1LL << deep)) ? 1 : 0;		ll res = 0;		if (bx == 1 && bk == 1) {			res += dfs(p->Next[0], x, k, deep - 1);		}		else if (bx == 1 && bk == 0) {			res += dfs(p->Next[1], x, k, deep - 1) + ((p->Next[0] != NULL) ? p->Next[0]->cnt : 0);		}		else if (bx == 0 && bk == 1) {			res += dfs(p->Next[1], x, k, deep - 1);		}		else {			res += dfs(p->Next[0], x, k, deep - 1) + ((p->Next[1] != NULL) ? p->Next[1]->cnt : 0);		}		return res;	}} trie;ll sum[MAXN];int main() {    //freopen("in.txt", "r", stdin);	int n, k;	scanf("%d%d", &n, &k);	for (int i = 1; i <= n; i++){		scanf("%I64d", &sum[i]);		sum[i] ^= sum[i - 1];	}	ll ans = 0;	trie.init();	trie.ins(0);	for (int i = 1; i <= n; i++) {		ll tmp = trie.dfs(trie.root, sum[i], k, maxbit);		//cout << tmp << endl;		ans += tmp;		trie.ins(sum[i]);	}	PRintf("%I64d/n", ans);	return 0;}