将每个可能的xor-sum子数组的和相加的算法 [英] Algorithm to add sum of every possible xor-sum sub-array

问题描述

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

I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

问题陈述

XOR-sum数组是对该子数组的所有数字进行XOR运算. 给您一个数组，您必须添加所有可能的XOR子数组.

XOR-sum array is to XOR all the numbers of that sub-array. An array is given to you, you have to add all possible such XOR-sub-array.

为了更好地理解，问题陈述也在此处.

For better understanding, question statement is here also.

示例

输入

数组:-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.

Hence the answer is 1 + 2 + 3 = 6.

我的代码

时间复杂度:-O(N ^ 2)，(效率低下，没有参加比赛)

Time Complexity :- O(N^2), (Inefficient one, didn't accpted in the competition)

#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;
}

问题:-

我在此链接

但是在这段代码中，我不理解下面的模块，请帮助我理解这一点.

But in this code, I didn't understand below module, please help me to understand that.

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;
        }

先谢谢了.寻找您的善意答复.

Thanks in advance. Looking for your kind reply.

推荐答案

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

Think of the numbers arranged in a Nx32 matrix, where each row represents a number in array and each column represents i'th bits of all the numbers. Now, effects of XOR operation are confined within a column. Therefore, we can separate each column, calculate the XOR-sum for that column and add it to the result.

我已分隔一列.如何计算此列内的XOR和?

为此，我们在此列中计算1的数量.让c表示一列中的数字1.然后，数字0将为N - c.要在列结果中产生1(0对最终结果没有影响)，对于c中的每个1，我们可以从N - c中取0，或者完全不取0.因此，在异或运算之后，每个1都有N - c + 1方式产生1.由于有c个1，所以XOR操作后的总数为1，是c * (N - c + 1).

For this purpose, we count the number of 1 in this column. Let c denote the number of 1 in a column. Then, number of 0 will be N - c. To produce 1 in column result (0s have no effect on final result), for each 1 from c, we can take a 0 from N - c, or take no 0 at all. Therefore, there are N - c + 1 ways for each 1 to produce 1 after XOR operation. As there are c 1s, Total number of 1 after XOR operation is c * (N - c + 1).

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

Each column contributes differently to the final result with respect to there position i. Therefore, multiply column-result with 2^i (1 << i) and add this to final result.

• 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).

• for (int i=0, p=1; i<30; i++, p<<=1)
  This loop separates the columns. It also makes p = 1 << i.
• if (A[j]&p) c++;
  This line counts number of 1 in a column.
• ret+=(long long)c*(N-c+1)*p;
  This elevates the column-result with respect to column position and add this to final result. Remember that, p = 1 << i (= 2^i).

自信心:我只解释了代码中所做的事情.我没有证据表明它将覆盖所有子阵列.

这篇关于将每个可能的xor-sum子数组的和相加的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！