Hi, today I learned Trie:D and I solved a easy problem. Here is my code on the problem
include
int const N = 1000002; int const BITS = 31;
int link[N * BITS][2]; int a[N], num[N * BITS];
int main() { int n, k; //read the cutest data:D scanf("%d%d", &n, &k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i = 1; i <= n; i++) a[i] ^= a[i — 1]; int freak = 2; int root = 1; long long ans = 0; for (int i = 0; i <= n; i++) { int v = root; //get all that less than K :D for (int b = BITS — 1; b >= 0 && v > 0; b--) { int curAi = (a[i] >> b) & 1; int curK = (k >> b) & 1; if (curK == 1) { if (link[v][curAi] > 0) { ans += num[link[v][curAi]]; } } v = link[v][curAi ^ curK]; } v = root;
//insert a[i] to trie:D for (int b = BITS - 1; b >= 0; b--) { num[v]++; int cur = (a[i] >> b) & 1; if (link[v][cur] == 0) { link[v][cur] = freak++; } v = link[v][cur]; } num[v]++;
} //ans get those less than K:D printf("%I64d\n", (long long) n * (n + 1) / 2 — ans); }
That's all. **** I will be back:D