如何报告子数组的索引，其xor为零？

Question

如何报告子数组的索引，其xor为零？

3

输入数组：5,2,7,100,1090,1,3,6,4,1062（从0开始编号的数组）

任务：对于给定的正整数序列，我想找出满足条件 1 ≤ i < j ≤ k ≤ N 并且 A[i]^…^A[j]−1=A[j]^A[j]+1^…^A[k] 的三元组 (i,j,k) 的数量，其中 ^ 表示按位异或。

我已经尝试使用 C++ 中的前缀异或数组和映射来解决这个问题，但是仍需要改进时间复杂度。

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]

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

- Obi Wan Kenobi

2

int A[n]; -- 这是无效的 C++ 代码。既然您已经在使用 std::vector，为什么不在这里也使用呢？std::vector<int> A(n);。 - PaulMcKenzie

@PaulMcKenzie 这是另一个问题，您能回答我的问题吗？ - Obi Wan Kenobi

你是新来的。评论区是用于评论的，而不是回答问题的。其次，一旦你像这样编写嵌套循环：for (int i = 0; i < size-1; ++i) { for (int k = i+1; k < size; ++k)，你就走错了方向。 - PaulMcKenzie

是的，我在这里是新手。 - Obi Wan Kenobi

@PaulMcKenzie 我知道有关于嵌套循环的内容，但我如何报告索引呢？ - Obi Wan Kenobi

1

我的观点是循环的时间复杂度为O(n*n)。如果你已经意识到了这一点，那么你应该尝试改进它。如果你从一个“在线评测”网站得到了这个问题，这些网站以出题让程序员给出天真、缓慢解决方案而闻名。他们希望你能跳出思维定势，想出一个不天真/不缓慢的解决方案。 - PaulMcKenzie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eesiraed · Accepted Answer

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

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部分后）。

现在来看一下复杂度，这个算法将是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]

注意，一个项的系数与该项的指数之间的关系由上述公式确定。因此，我们可以计算这个缩短的表达式，而不是遍历每一对元素。在原始问题中，您需要为每一对元素减去一个，因此我们可以从结果中减去元素对的数量。