Necesito ayuda con un problema que he reducido a lo siguiente. Tengo N números de 30 bits, de modo que el XOR combinado de todos ellos es distinto de cero. Necesito agregar un valor no negativo (0 o más) a cada uno de los N números, de modo que el XOR combinado de los nuevos números se convierta en 0, bajo la restricción de que el valor total de la suma (no el número de adiciones) se minimiza .

Por ejemplo, si tuviera números (01010)2, (01011)2 y (01100)2 Como tres números (N = 3). Entonces, su XOR combinado es (01101)2. Podríamos agregar algunos números de la siguiente manera:

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

Ahora, el XOR total de los nuevos números es 0, y la suma total es 21 (= + 1 + 16 + 4). Este valor de suma total tiene que serminimizado (Podría haber una mejor distribución que reduzca este total, pero esto es solo unaejemplo).

Estos números son de 30 bits cada uno, por lo que los números podrían ser grandes, y N <= 15. Realmente agradecería si alguien pudiera mostrar alguna forma eficiente de resolver esto. Sospecho que una solución de DP es posible, pero no pude formular nada.

¡Gracias!