找到一個給定的異或子集的數量

我有一個數組有10^5個元素，其中每個元素都在[0，1023]。我必須找到一個數組的子集的數量，使得元素的XOR是Q.（對於Q> 1023，答案是0）。我想出了這個O（N * 1024）方法找到一個給定的異或子集的數量

for (int i = 1; i <= n; i++) 
{ 
    int a = F[i]; 
    for (int j = 0; j < 1024; j++) 
    { 
     ways[i][j] = ways[i-1][j] + ways[i-1][j^a]; 
     if (ways[i][j] >= mod) 
      ways[i][j] -= mod; 
    } 
}

由於元件在範圍高達1023，可我維持的Frequency F[i] ,陣列減少上述代碼高達O（1024 * 1024）。 這是可能的，頻率數組可能會有用嗎？

來源

2015-12-07 Sunny

子集必須是一定的大小？它們是由陣列中的相鄰元素製成的嗎？ – m69

所以你有'F'這是一個0到1,023之間的隨機數組。你有'Q'這是一個在同一範圍內的隨機數。你想知道插入'F [x]^F [y]'的多少個不同的x，y組合可以等於'Q'？例如：如果'F = [0,1,1,2,2,2,3,3,3,3]'和'Q = 3'，那麼'ways'應該是10？（1 * 4 + 2 * 3） – dtudury

@ m69子集可以是任意大小'2^n'子集可能 – Sunny

那麼，答案几乎總是2 ^（N-10）

首先，注意，如果您XOR一個元素到另一個，它並沒有改變XOR到Q.

子集數

證明：可以說你有你的A的大小爲N的數組，以及一些XOR爲特定值的子集。然後你做A [i]^= A [j]，i！= j。現在，爲了修復所有子集，以便它們與相同的值異或，您只需找到包含A [i]的那些子集，並在其中切換A [j]。因此，我們所做的異或並不影響與任何特定值異或的子集總數。

所以......

找到最大的元素，並將其移動到位置0然後異或成所有具有相同的MSB（最顯著位）的其他元素，從而使A [0 ]是具有最大MSB的唯一元素。
找到最大的剩餘元素，將其移到位置1，並將其異或爲所有其餘具有相同MSB的元素，因此A [1]將是具有第二大MSB的唯一元素。
繼續第三大MSB等等，儘可能多次。最多有10個非零元素，全部使用不同的MSB，其餘元素全部爲零。

假設你最終得到M個非零元素。如果你可以通過將這些元素異或來製作Q，那麼只有一種方法可以做到這一點。其他N-M元素全部爲零，因此您可以在不改變總XOR值的情況下將它們添加到任何子集或從其中刪除。因此，如果你可以製作Q，那麼將會有2 ^（NM）個子集與XOR異或。

如果你不能通過對這些非零元素進行異或操作來生成Q，那麼XOR Q是0.

有關此過程的更多信息，谷歌「高斯消除」

來源

2016-01-03 06:59:31

找到一個給定的異或子集的數量

回答

相關問題