Advertisement
ZOOOO

Untitled

Jan 27th, 2016
3,699
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. //нулевой xor
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. struct BTrie {
  7. struct BTrie *next[2];
  8. int v;
  9. };
  10.  
  11. typedef struct BTrie BT;
  12.  
  13. int checkbit(unsigned int n, int b) {
  14. return (n & (1 << b)) >> b;
  15. }
  16.  
  17. BT *initBT() {
  18. return calloc(1, sizeof(BT));
  19. }
  20.  
  21. void addBT(BT *b, int v) {
  22. BT *p = b;
  23. for(int i = 0; i < sizeof(int) * 8; i++) {
  24. int bit = checkbit(v, i);
  25. if(!(p->next[bit]))
  26. p->next[bit] = calloc(1, sizeof(BT));
  27. p = p->next[bit];
  28. }
  29. if(!v && !p->v)
  30. p->v++;
  31. p->v++;
  32. }
  33.  
  34. int forEachBT(BT *b, int level) {
  35. if(level) {
  36. int res = 0;
  37. if(b->next[0])
  38. res += forEachBT(b->next[0], level - 1);
  39. if(b->next[1])
  40. res += forEachBT(b->next[1], level - 1);
  41. return res;
  42. } else {
  43. int v = b->v - 1;
  44. return v * (v + 1) / 2;
  45. }
  46. }
  47.  
  48. void freeBT(BT *b) {
  49. if(b->next[0])
  50. freeBT(b->next[0]);
  51. if(b->next[1])
  52. freeBT(b->next[1]);
  53. free(b);
  54. }
  55.  
  56. int main(void) {
  57. int n, xor = 0;
  58. scanf("%d", &n);
  59. BT *bt = initBT();
  60. for(int i = 0; i < n; i++) {
  61. int tmp;
  62. scanf("%d", &tmp);
  63. xor ^= tmp;
  64. addBT(bt, xor);
  65. }
  66. printf("%d\n", forEachBT(bt, sizeof(int) * 8));
  67. freeBT(bt);
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement