每日一题：异或

题目

给定整数 $m$ 以及 $n$ 各数字 $A_1,A_2,..A_n$，将数列 $A$ 中所有元素两两异或，共能得到 $n(n-1)/2$ 个结果，请求出这些结果中大于 $m$ 的有多少个。

Solution

为了避免重复计算，字典树可以边维护边插入，先查询之前有多少个数与当前数 $x$ 异或和大于 $m$，我们从高位向低位枚举，对于两个数的同一个二进制位，需要分四种情况讨论：

1. $x_i = 1, m_i = 1$，则查询的数当前位必须为 $0$ 才可。

2. $x_i = 0, m_i = 1$，则查询的数当前位必须为 $1$ 才可。

3. $x_i = 1, m_i = 0$，则查询数当前位为 $0$ 的直接满足条件计入答案，当前位为 $1$ 的继续向下查找。

4. $x_i = 0, m_i = 0$，则查询数当前位为 $1$ 的直接满足条件计入答案，当前位为 $0$ 的继续向下查找。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 5;
typedef long long ll;
int n, m, idx, cnt[N], trie[N][2];

void insert(int x) {
  int p = 0, y;
  for (int i = 31; ~i; i--) {
    y = x >> i & 1;
    int &s = trie[p][y];
    if (!s) s = ++idx;
    p = s;
    cnt[p]++;
  }
}

int query(int x) {
  int p = 0, p1, sum = 0;
  for (int i = 31; ~i; i--) {
    int y = x >> i & 1;
    int z = m >> i & 1;
    if (y == 1 && z == 1) {
      p = trie[p][0];
    } else if (y == 0 && z == 1) {
      p = trie[p][1];
    } else if (y == 1 && z == 0) {
      p1 = trie[p][0];
      p = trie[p][1];
      if (p1) sum += cnt[p1];
    } else if (y == 0 && z == 0) {
      p1 = trie[p][1];
      p = trie[p][0];
      if (p1) sum += cnt[p1];
    }
    if (!p) break;
  }
  return sum;
}

int main() {
  long long res = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    res += query(x);
    insert(x);
  }
  printf("%lld\n", res);
  return 0;
}