Finden der Anzahl von Subsets mit einem gegebenen Xor - Algorithmus, Datenstrukturen, xor

Ich habe ein Array mit 10 ^ 5 Elementen, wobei jedes Element in [0, 1023] steht. Ich muss die Anzahl der Teilmengen eines Arrays finden, so dass XOR des Elements Q ist. (Für Q> 1023 ist die Antwort 0). Ich bin darauf gekommen O (N * 1024) Annäherung

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

Da Elemente im Bereich bis 1023 sind, könnte ich ein Array von Frequency F[i] , Reduziere den obigen Code bis zu O (1024 * 1024). Ist das möglich, kann Frequenz-Array nützlich sein?

Antworten:

Nun, die Antwort ist fast immer 2 ^ (N-10)

Beachten Sie zuerst, dass wenn Sie ein Element in ein anderes XOR-Element konvertieren, es die Anzahl der Teilmengen, die XOR zu Q sind, nicht ändert.

Beweis dafür: Nehmen wir an, Sie haben Ihr Array A der Größe N und eine Reihe von Subsets, die XOR zu bestimmten Werten haben. Dann tust du A [i] ^ = A [j], mit i! = J. Nun, um alle Teilmengen so zu fixieren, dass sie an die gleichen Werte XOR binden, finden Sie nur diejenigen, die A [i] enthalten, und schalten A [j] in ihnen um. Also hat das XOR, das wir gemacht haben, keinen Einfluss auf die Gesamtzahl der Teilmengen, die XOR auf einen bestimmten Wert hat.

Damit...

1. Finden Sie das größte Element und verschieben Sie es in Position 0. Dann XOR es in alle anderen Elemente, die das gleiche MSB (höchstwertige Bit) haben, so dass A [0] das einzige Element mit dem größten MSB ist.

2. Finden Sie das größte verbleibende Element, verschieben Sie es auf Position 1 und XOR in alle übrigen Elemente mit demselben MSB, so dass A [1] das einzige Element mit dem zweitgrößten MSB ist.

3. Fahren Sie so oft wie möglich mit dem drittgrößten MSB usw. fort. Sie haben höchstens 10 Elemente ungleich null, die alle unterschiedliche MSBs haben, und die restlichen Elemente sind alle null.

Nehmen wir an, Sie haben M Elemente ungleich null. Wenn Sie Q durch XOR-Verknüpfung dieser Elemente erstellen können, gibt es nur eine Möglichkeit. Die anderen N-M-Elemente sind alle null, so dass Sie sie aus jeder Untermenge hinzufügen oder entfernen können, ohne den gesamten XOR-Wert zu ändern. Also, wenn Sie Q machen können, dann wird es 2 ^ (N-M) Untermengen geben, die XOR zu Q.

Wenn Sie Q nicht durch XOR-Verknüpfung dieser Nicht-Null-Elemente erzeugen können, dann ist natürlich die Anzahl der Teilmengen, die XOR zu Q ist, 0.

Für weitere Informationen zu diesem Verfahren google "Gaussian Elimination"