Potrzebuję pomocy z problemem, który zredukowałem do następujących. Mam N 30 liczb bitowych, tak że łączny XOR wszystkich z nich jest niezerowy. Muszę dodać wartość nieujemną (0 lub więcej) do każdej z N liczb, tak aby połączony XOR nowych liczb stał się 0, pod warunkiem, że całkowita wartość dodana (nie liczba dodatków) jest zminimalizowana .

Na przykład, gdybym miał numery (01010)2, (01011)2 i (01100)2 jako trzy liczby (N = 3). Następnie ich połączone XOR wynosi (01101)2. Możemy dodać kilka liczb w następujący sposób:

(01010)2 + (00001)2 = (01011)2 : (+1)(01011)2 + (10000)2 = (11011)2 : (+16)(01100)2 + (00100)2 = (10000)2 : (+4)

Teraz całkowity XOR nowych liczb wynosi 0, a całkowity dodatek wynosi 21 (= + 1 + 16 + 4). Ta całkowita wartość dodana musi byćzminimalizowany (może istnieć lepsza dystrybucja, która redukuje tę sumę, ale to jest po prostuprzykład).

Liczby te są po 30 bitów każdy, więc liczby mogą być duże, a N <= 15. Naprawdę bym to docenił, gdyby ktoś mógł pokazać jakiś skuteczny sposób rozwiązania tego problemu. Podejrzewam, że rozwiązanie DP jest możliwe, ale nie mogłem niczego sformułować.

Dzięki!