添加每个可能的xor-sum子数组之和的算法

Question

我参加了一个算法竞赛.我陷入了一个问题,我在这里问同样的问题.

问题陈述

XOR-sum数组是对该子数组的所有数字进行异或.给你一个数组,你必须添加所有可能的这样的XOR子数组.

为了更好地理解,问题陈述也在这里.

例

输入

数组: - 1 2

输出: - 6

说明

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2和 F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3.

因此答案是1 + 2 + 3 = 6.

我的代码

时间复杂度: - O(N ^ 2),(效率低,未参加竞赛)

#include<iostream>

using namespace std;

long long int input[100001];

main() {
    int T;
    int N;
    long long int val;
    long long int temp = 0;
    long long int answer = 0;
    cin >> T;

    while(T--) {
        cin >> N;
        for(int i = 0; i < N; i++) {
            cin >> val;
            temp = temp^val;
            answer += temp;
            input[i] = temp;
        }

        for( int i = 0; i < N; i++ ) {
            for( int j = i+1; j < N; j++ ) {
                answer += input[i]^input[j];
            }
        }
        cout << answer << endl;
        answer = 0;
        temp = 0;
    }
    return 0;
}

题:-

我在这个链接上看到了这个问题的最佳解决方案

但是在这段代码中,我不明白下面的模块,请帮我理解.

for (int i=0, p=1; i<30; i++, p<<=1) {
            int c=0;
            for (int j=0; j<=N; j++) {
                if (A[j]&p) c++;
            }
            ret+=(long long)c*(N-c+1)*p;
        }

提前致谢.寻找你的回复.

Answer 1

想象一下排列在 Nx32 矩阵中的数字，其中每行代表数组中的一个数字，每列代表所有数字的第 i 位。现在，异或运算的效果被限制在列内。因此，我们可以分离每一列，计算该列的异或和并将其添加到结果中。

我已经分开了一个专栏。如何计算该列中的异或和？

为此，我们计算该列中 1 的数量。让我们c表示一列中 1 的数量。那么 0 的个数就是N - c。为了在列结果中产生 1（0 对最终结果没有影响），对于 中的每个 1 c，我们可以从 中取 0 N - c，或者根本不取 0。因此，N - c + 1每个1经过异或运算后产生1是有办法的。由于有c1，所以异或运算后 1 的总数为c * (N - c + 1)。

每列对于其位置的最终结果的贡献不同i。因此，将列结果乘以2^i( 1 << i) 并将其添加到最终结果中。

• for (int i=0, p=1; i<30; i++, p<<=1)
  该循环将列分开。这也使得p = 1 << i.
• if (A[j]&p) c++;
  该行计算一列中 1 的数量。
• ret+=(long long)c*(N-c+1)*p;
  这会相对于列位置提升列结果并将其添加到最终结果中。请记住，p = 1 << i(= 2^i)。

坦白：我只是解释了代码中做了什么。我没有证据表明这将覆盖所有子数组。