Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //нулевой xor
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- struct BTrie {
- struct BTrie *next[2];
- int v;
- };
- typedef struct BTrie BT;
- int checkbit(unsigned int n, int b) {
- return (n & (1 << b)) >> b;
- }
- BT *initBT() {
- return calloc(1, sizeof(BT));
- }
- void addBT(BT *b, int v) {
- BT *p = b;
- for(int i = 0; i < sizeof(int) * 8; i++) {
- int bit = checkbit(v, i);
- if(!(p->next[bit]))
- p->next[bit] = calloc(1, sizeof(BT));
- p = p->next[bit];
- }
- if(!v && !p->v)
- p->v++;
- p->v++;
- }
- int forEachBT(BT *b, int level) {
- if(level) {
- int res = 0;
- if(b->next[0])
- res += forEachBT(b->next[0], level - 1);
- if(b->next[1])
- res += forEachBT(b->next[1], level - 1);
- return res;
- } else {
- int v = b->v - 1;
- return v * (v + 1) / 2;
- }
- }
- void freeBT(BT *b) {
- if(b->next[0])
- freeBT(b->next[0]);
- if(b->next[1])
- freeBT(b->next[1]);
- free(b);
- }
- int main(void) {
- int n, xor = 0;
- scanf("%d", &n);
- BT *bt = initBT();
- for(int i = 0; i < n; i++) {
- int tmp;
- scanf("%d", &tmp);
- xor ^= tmp;
- addBT(bt, xor);
- }
- printf("%d\n", forEachBT(bt, sizeof(int) * 8));
- freeBT(bt);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement