Hľadanie množstva podsúboru s daným Xor - algoritmom, dátovými štruktúrami, xor

Mám pole s 10 ^ 5 prvkami, kde je každý prvok v [0, 1023]. Musím nájsť taký počet podmnožín poľa, že XOR prvku je Q. (pre Q> 1023 je odpoveď 0). Prišiel som s týmto Prístup 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;
}
}

Pretože prvky sú v rozsahu až 1023, mohol by som zachovať pole Frequency F[i] , znížiť vyššie uvedený kód až O (1024 * 1024). Je to možné, môže byť frekvenčné pole užitočné?

odpovede:

Odpoveď je takmer vždy 2 ^ (N-10)

Najprv si uvedomte, že ak XOR použijete na uskutočnenie jedného prvku, nezmení to počet podmnožín, ktoré obsahujú XOR, na Q.

Dôkaz toho:Povedzme, že máte svoje pole A veľkosti N a kopu podmnožín, ktoré XOR zodpovedajú konkrétnym hodnotám. Potom urobíte A [i] ^ = A [j] s i! = J. Ak chcete teraz opraviť všetky podmnožiny tak, aby obsahovali XOR na rovnaké hodnoty, nájdite iba tie, ktoré obsahujú A [i], a prepnite v nich A [j]. Takže XOR, ktorý sme urobili, neovplyvní celkový počet podmnožín, ktoré XOR majú, na konkrétnu hodnotu.

Takže ...

1. Nájdite najväčší prvok a presuňte ho do polohy 0. Potom ho XOR vložte do všetkých ostatných prvkov, ktoré majú rovnaký MSB (najvýznamnejší bit), takže A [0] je jediný prvok s najväčším MSB.

2. Nájdite najväčší zostávajúci prvok presunutím do polohy 1 a XOR do všetkých zostávajúcich prvkov s rovnakým MSB, takže A [1] bude jediným prvkom s druhým najväčším MSB.

3. Pokračujte s 3. najväčším MSB atď., Koľkokrát môžete. Nakoniec získate najviac 10 nenulových prvkov, všetky s rôznymi MSB a zvyšné prvky budú všetky nulové.

Povedzme, že skončíte s M nenulovými prvkami.Ak môžete vytvoriť Q spojením týchto prvkov XOR, potom bude existovať iba jeden spôsob, ako to urobiť. Ostatné prvky N-M sú všetky nulové, takže ich môžete pridať alebo odstrániť z ľubovoľnej podmnožiny bez zmeny celkovej hodnoty XOR. Takže ak môžete vytvoriť Q, potom budú existovať 2 ^ (N-M) podmnožiny, ktoré budú XOR až Q.

Ak nemôžete Q vytvoriť XORingom týchto nenulových prvkov, potom počet podmnožín, ktoré majú XOR až Q, je samozrejme 0.

Ďalšie informácie o tomto postupe nájdete na stránkach google „Gaussian Elimination“.