Мне нужна помощь с проблемой, которую я сократил до следующего. У меня есть N 30-битных чисел, так что объединенный XOR всех их ненулевой. Мне нужно добавить неотрицательное (0 или более) значение для каждого из N чисел, так что объединенное XOR новых чисел становится равным 0, при условии, что общее добавленное значение (а не количество сложений) сведено к минимуму ,

Например, если у меня были номера (01010) 2, (01011) 2 и (01100) 2 как три числа (N = 3). Тогда их объединенное XOR равно (01101) 2, Мы могли бы добавить несколько чисел следующим образом:

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

Теперь общее XOR новых чисел равно 0, а общее сложение равно 21 (= + 1 + 16 + 4). Эта общая добавленная стоимость должна бытьсвести к минимуму (могло бы быть лучшее распределение, которое уменьшает это общее количество, но это простопример).

Эти числа по 30 бит, поэтому они могут быть большими, и N <= 15. Я был бы очень признателен, если бы кто-нибудь смог показать какой-нибудь эффективный способ решения этой проблемы. Я подозреваю, что решение DP возможно, но я не мог сформулировать что-либо.

Спасибо!