Encontrar XOR de todos los subconjuntos de

Question

Nota del moderador: este es un ir concurso problema. Por protocolo habitual, las respuestas han sido ocultados y la pregunta es bloqueado hasta la fecha de finalización del concurso. (21.03.2014)

Dada una lista que contiene N enteros, Cómo encontrar el XOR_SUM de todos los no vacía de subconjuntos de la lista.

E. g. XOR_SUM de lista a tener tres elementos de {X1, X2, X3} puede ser dada como sigue. Todos no vacía de subconjuntos será {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

EJEMPLO : si N=3 y la lista [1,2,3] aquí la respuesta será de 12 como de Su voluntad de ser 7 no vacía de subconjuntos cuya XOR es la siguiente

1 = 1
2 = 2
3 = 3
1^2 = 3
2^3 = 1
3^1 = 2
1^2^3 = 0

De modo que la suma de todos los XORs se 12.

Answer 1

Considere la posibilidad de una posición de bit a la vez. Cómo muchos de los términos que tienen el bit $i$? Los términos que tienen el bit $i$ son exactamente las mismas que corresponden a un subconjunto que contiene un extraño número de entradas que tienen poco $i$.

• Si hay alguna entrada que tiene poco $i$, luego de exactamente la mitad de la $2^N$ posibles subconjuntos será de esta forma, y así contribuirán $2^{N-1+i}$ a la suma final.

• Por otro lado, si no hay entrada de bits $i$, entonces, por supuesto, no se cuanto tendrá de que un conjunto de bits.

Sumando los aportes de $2^{N-1+i}$ por cada posición de bit es bastante fácil -- la suma final simplemente se $2^{N-1}$ tiempos de bit O de todos los insumos.