C++程序计算唯一三元组的XOR为零

什么是XOR？

XOR，即异或，是一种逻辑运算符，表示当两个比特位不同时输出1，否则输出0。如下是XOR运算的真值表：

输入A	输入B	输出
0	0	0
0	1	1
1	0	1
1	1	0

在C++中，XOR可以用“^”来表示。

什么是三元组？

在数学中，三元组指的是有序的三个元素组成的集合。例如，(3, 2, 1) 和 (1, 2, 3)是两个不同的三元组。

在计算机科学中，三元组通常指的是由三个整数构成的有序组。例如，(3, 2, 1)和(1, 2, 3)在计算机科学中被视为相同的三元组。

什么是计算唯一三元组的XOR为零？

“计算唯一三元组的XOR为零”可以理解为在给定的一组三元组中，寻找满足以下条件的三元组数量：
– 三元组中的所有元素使用XOR运算后的值为零。
– 同一个三元组不重复计算。

实现

下面是一个使用Brute-Force(暴力枚举)的方法的伪代码：

unique_triplets_num = 0
for i in range(1, n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if (arr[i] ^ arr[j] ^ arr[k] == 0):
        unique_triplets_num = unique_triplets_num + 1
return unique_triplets_num

其中，n指三元组总数，arr表示所有三元组的数组。

但是，这个算法的时间复杂度为O(n^3)，当n很大时，运算耗时较长。

为了提高效率，可以使用一种称为哈希表的数据结构。下面是使用哈希表实现的代码：

typedef unsigned long long ULL;
ULL cnt[1 << 20];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < (1 << 20); j++) {
            if (j >> i & 1) {
                cnt[j] += cnt[j ^ (1 << i)];
            }
        }
    }

    ULL ans = 0;
    for (int i = 0; i < (1 << 20); i++) {
        ans += cnt[i] * (cnt[i] - 1) / 2 * (cnt[i] - 2) / 3;
    }
    cout << ans << endl;
    return 0;
}

这个算法的时间复杂度为O(nlogn)。