Moje rozwiązanie dostało 7 punktów, ale nie wiem jaką to ma złożoność.

Dla każdej spójnej składowej trzymam drzewo decyzyjne, które odpowiada na pytania: dla danej konfiguracji, ile jest początkowych konfiguracji, które do niej prowadzą, modulo 2. Drzewo zawiera pytania o pozycje w jakiejś kolejności (gotowy lub nie).

Gdy spójne się łączą, to łączę drzewa: w liściach jednego drzewa wstawiam wskaźniki do drugiego drzewa.

Gdy mamy rozkaz (a, b), to przekształcam drzewo tak, żeby pierwsze pytania były o pozycje a, b. I teraz liczę xora dwóch poddrzew (a tak, b nie) xor (a nie, b tak) i wstawiam to jako poddrzewo (a nie, b tak).

Cachuję wszystko, żeby nie liczyć dwa razy tego samego:
* nigdy nie tworzę dwóch identycznych poddrzew (cachuję pary dzieci i szukam przy tworzeniu nowego poddrzewa)
* wysuwanie pytania o daną pozycję do korzenia poddrzewa
* łączenie poddrzew
* xorowanie poddrzew

Moje rozwiązanie wygląda jakoś tak:

Dla każdej osoby będziemy w każdym momencie wiedzieć, czy ma '0', '1', czy też nic nie wiemy '?'. Zaczynamy od stanu, w którym na każdej pozycji znajduje się '?'.

Gdy krawędź prowadzi ze '?' do '?', to ponieważ każdy stan, w którym na pozycji a był '0', a na pozycji b był '1', będzie miał odpowiadający stan, w którym na pozycji a będzie '1', a na pozycji b również '1'. Oba stany będą miały tę samą liczebność, więc po przejściu tą krawędzią każdy stan, w którym a i b mają różne wartości, będzie miał parzystą liczbę możliwości.

Możemy więc założyć, że wartości na pozycjach a i b są równe. Schodzimy rekurencyjnie do stanu, w którym oba są '1' lub oba są '0'.

Jeśli krawędź prowadzi z '1' do '?', '? do '0', lub '1' do '0', to po prostu zamieniamy te wartości miejscami.

Ponieważ zejście w dół zmniejsza liczbę '?' o 2, to złożoność takiej rekurencji będzie O(2^(n/2)*m).