如何报告异或为零的子数组的索引？

Question

输入数组：5,2,7,100,1090,1,3,6,4,1062（0-索引数组）

Task ：对于给定的正整数序列，我想找到满足 1 ≤ i < j ≤ k ≤ N 的三元组 (i,j,k) 的数量和

A[i]^…^A[j]−1=A[j]^A[j]+1^…^A[k], 其中 ^ 表示按位异或。

我已经在 C++ 中使用 prefix_xor 数组和映射尝试了这个问题，但我仍然需要提高时间复杂度。

cin >> n;
int A[n];
ll count = 0;
unordered_map<int, vector<int>> map_table;
for (int i = 0; i < n; ++i)
    cin >> A[i];
map_table[A[0]].push_back(0);
for (int i = 1; i < n; ++i)
{
    A[i] = A[i] ^ A[i-1];
    if (!A[i])
        count += i;
    map_table[A[i]].push_back(i);
}
unordered_map<int, vector<int>>::iterator i2; 
for (i2 = map_table.begin(); i2 != map_table.end(); ++i2)
{
    int size = i2->second.size();
    if (size >= 2)
    {
        for (int i = 0; i < size-1; ++i)
        {
            for (int k = i+1; k < size; ++k)
                count += ((i2->second[k])-(i2->second[i])-1);
        }
    }
}
cout << count << '\n';

在这个例子中答案是 20

[0,2], [5,8], [0,9], [3,9]

异或(5, 2, 7) = 0;异或 (1, 3, 6, 4) = 0;异或(100, 1090, .... 1062) = 0; XOR(5, 2, 7 .... 1062) = 0

Answer 1

我将优化您的这部分代码：

for (int i = 0; i < size-1; ++i)
{
    for (int k = i+1; k < size; ++k)
        count += ((i2->second[k])-(i2->second[i])-1);
}

请注意，您基本上是在尝试求出数组 (i2->second) 中每对数字之间的差之和。您在 O(n^2) 中执行此操作，但如果我们稍微操纵一下公式，我们可以更快地完成。

假设我们的数组（我们暂时称之为 a）的长度为 n。我们现在只关注第 i 个元素（从 0 开始索引），我们将计算它被添加到总和和从总和中减去的总次数。对于每 j < i，总和将包括 a[i] - a[j]。同样，对于每个j > i，总和包括a[j] - a[i]。在前一种情况下，a[i] 总共添加了 i 次。在后一种情况下，a[i] 总共被减去 n - i - 1 次。所以a[i]在总和（加的次数减去减的次数）中的系数为i - (n - i - 1) == 2 * i - n + 1。将其乘以每个元素并将所有内容相加得到答案（在调整 -1 部分后）。

考虑到复杂性，对于一个前缀 XOR 值，此算法将是 O(n)，其中 n 是该值出现的次数。由于每个前缀 XOR 值出现的次数将加到原始数组的长度，因此创建映射后总复杂度是线性的。

这是请求的示例：

假设数组有五个元素，a[0...4]。如果我们写出您要计算的总和，它看起来像这样：

  (a[1] - a[0]) + (a[2] - a[0]) + (a[3] - a[0]) + (a[4] - a[0])
+ (a[2] - a[1]) + (a[3] - a[1]) + (a[4] - a[1])
+ (a[3] - a[2]) + (a[4] - a[2])
+ (a[4] - a[3])

我们稍后再处理 -1 的问题。如果我们将类似的术语分组，它看起来像这样：

-4 * a[0] + -2 * a[1] + 0 * a[2] + 2 * a[3] + 4 * a[4]

注意一个项的系数通过上面提到的公式与该项的索引相关联。因此，我们不是迭代每一对元素，而是计算这个缩短的表达式。原题中每对元素都需要减1，所以我们直接减去元素对的个数就可以了。

如何报告异或为零的子数组的索引？

How to report the indices of a sub array whose xor is zero?

c++

arrays

xor