添加每個可能的xor-sum子陣列的總和的算法

Question

我參加了一個算法競賽。我陷入了一個問題，我在這裏也一樣問。

問題陳述

XOR求和陣列是進行XOR該子陣列的所有的數字。 給你一個數組，你必須添加所有可能的這種異或子數組。

爲了更好地理解，問題陳述也是here。

例

輸入

陣列： - 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），（一個低效，並沒有在比賽中accpted）

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

問題： -

我看到this link

這個問題的最佳解決方案，但在此代碼，我不明白以下模塊，請幫我理解這一點。

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

想象一下排列在N×32矩陣中的數字，其中每一行代表數組中的一個數字，每列代表所有數字的第i位。現在，XOR操作的效果被限制在一列中。因此，我們可以將每列分開，計算該列的異或總和並將其添加到結果中。

我已經分開了一列。如何計算此列中的異或總和？

爲此，我們計算此列中的數目1。假設c表示列中的數字1。然後，0的編號將是N - c。要在列結果中產生1（0對最終結果沒有影響），對於c中的每個1，我們可以從N - c取0，或者根本不取0。因此，在異或操作之後，每個1產生1的方式有N - c + 1。由於有c 1，異或操作後的總共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）。

CONFESSION：我只解釋了在代碼中做了什麼。我沒有證據證明這將覆蓋所有的子陣列。

Answer 2

據我所知，您提供的鏈接代碼不是最好的解決方案，甚至沒有工作的解決方案。您從該鏈接複製的代碼似乎是有道理的，但先於複製的代碼，當值被讀入A，它們是由之前讀取值進行異或運算：

for (int i = 1; i <= N; i++) 
{ 
    scanf("%d", &A[i]); 
    A[i] ^= A[i - 1]; 
} 

...意義以下輸入：

1 
4 
1 2 3 4 

...被存儲到A像這樣：

A[0]: 00000000000000000000000000000000 = 0 
A[1]: 00000000000000000000000000000001 = 1 
A[2]: 00000000000000000000000000000011 = 3 
A[3]: 00000000000000000000000000000000 = 0 
A[4]: 00000000000000000000000000000100 = 4 

對於前面的輸入，正確的答案應該是：

F(1, 1) + F(1, 2) + F(2, 2) + F(1, 3) + F(2, 3) + F(3, 3) + F(1, 4) + F(2, 4) + F(3, 4) + F(4, 4) 
= 1 + 3 + 2 + 2 + 1 + 3 + 5 + 6 + 7 + 4 
= 34 

...但這裏是我們得到使用您發佈的 「最好的之一」 的c *（N（總和算法 - c + 1）* 2^i從i = 0至i = 29 ）

2 * (4 - 2 + 1) * 1 + 1 * (4 - 1 + 1) * 2 + 1 * (4 - 1 + 1) * 4 
= 6 + 8 + 16 
= 30 

所以這是關閉的4個，因此它不是一個工作解決問題的辦法，更不用說最好的有效的解決方案。

注意，如果值沒有被異或，當他們閱讀，這裏就是會在A：

A[0]: 00000000000000000000000000000000 = 0 
A[1]: 00000000000000000000000000000001 = 1 
A[2]: 00000000000000000000000000000010 = 2 
A[3]: 00000000000000000000000000000011 = 3 
A[4]: 00000000000000000000000000000100 = 4 

所以後來的c *（N公式總和 - c + 1 ）* 2^i從i = 0至i = 29會給：

2 * (4 - 2 + 1) * 1 + 2 * (4 - 2 + 1) * 2 + 1 * (4 - 1 + 1) * 4 
= 6 + 12 + 16 
= 34 

...這是正確的答案，根據您鏈接的網站上的問題聲明。我認爲這就是爲什麼我們看到了與您發佈的代碼一致的答案 - 即使前面的代碼（在您鏈接的頁面中找到）導致整個程序錯誤，您發佈的代碼也是有意義的。

Answer 3

我想你留下了一些非常重要的細節：

int A[MAXN];// the arrays contain int values 
//xor all the elements of the array as you read them 
for (int i=1; i<=N; i++) { 
    scanf("%d", &A[i]); 
    A[i]^=A[i-1]; 
} 

讀取輸入後，你將結束：

A[0] = A[0] 
A[1] = A[1]^A[0] 
... 
A[N] = A[N]^A[N-1]^...^A[0] 

這是O（N）的，你得到免費基本上，因爲你必須閱讀輸入。 這需要謹慎或XOR部分。現在你只剩下問題的SUM部分了。 你有N個INT號（32位），這裏是你展示了部分來自於：

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

對於你去通過陣列和計數的1的數量，並將它們添加到最終結果的每一位。

這部分是O（30 * N），它仍然是線性時間，所以O（N）。這比O（N^2）好。

希望對此有所瞭解。