XOR 문제에 접근하기 위해 반드시 필요한 스킬1 - 기본 성질 -

1. 기본 성질

 

정수 x,y,z에 대하여...

 

$$ x \oplus 0 = x $$

 

$$ x \oplus x = 0 $$

 

$$ x \oplus y = y \oplus x $$

 

$$ (x \oplus y) \oplus z = x \oplus (y \oplus z)$$

 

사실 교환법칙, 결합법칙이 성립하고 0을 xor하면 그대로 나오고 자기자신을 xor하면 0이 나온다는거 아는데

 

만약 n개의 원소 a1,a2,a3,...,an에 대하여.. a1 ^ a2 ^ a3 ^ ... ^ an을 생각해보자.

 

a2 ^ a3 ^ a4 ^ ... ^ an의 값을 알고 싶다면 어떻게 해야할까?

 

a1+a2+a3+...+an을 알고있다면 그냥 a1을 뺀다면 되는데 xor에서는 이런 빼기 연산이 있는건가?

 

다시 a2,a3,..,an을 차례대로 xor해야하나?

 

그럴 필요 없이 a1을 xor하면 된다.

 

(a1 ^ a2 ^ ... ^ an) ^ a1 = (a1 ^ a1) ^ (a2 ^ ... ^ an) = 0 ^ (a2 ^ ... ^ an) = (a2 ^ ... ^ an)

 

 

2. 문제

 

11895번: 속이기 (acmicpc.net)

11895번: 속이기

 

 

3. 풀이

 

X1 ^ X2 ^ ... Xk = Y1 ^ Y2 ^ ... Y(n-k)라고 하자.

 

양변에 (Y1 ^ Y2 ^ ... Y(n-k))를 XOR한다면... 

 

(X1 ^ X2 ^ ... ^ Xk) ^ (Y1 ^ Y2 ^ ... Y(n-k)) = (Y1 ^ Y2 ^ ... Y(n-k)) ^ (Y1 ^ Y2 ^ ... Y(n-k))

 

우변은 같은 수끼리 XOR했으므로 0이다.

 

좌변은 교환법칙, 결합법칙을 이용하면.. 배열 A의 모든 원소들의 XOR과 같다.

 

(A1 ^ A2 ^ ... An) = 0

 

따라서 문제에서 주어진 상황 A의 원소를 두 부분으로 나눠서 X1 ^ X2 ^ ... Xk = Y1 ^ Y2 ^ ... Y(n-k)이 가능할려면

 

A의 모든 원소들에 대해 XOR했을 때 0이어야한다.

 

그리고 만약에 (A1 ^ A2 ^ ... An) = 0이라고 하자.

 

A1 <= A2 <= ... <= An이라고 했을때, 양변에 A1을 XOR한다면... 

 

(A1 ^ A2 ^ ... ^An) ^ A1 = 0 ^ A1

 

우변은 0과 XOR하면 그대로 나오므로 A1

 

좌변은 교환법칙과 결합법칙, 0과 xor, 같은 수끼리 xor의 성질을 이용해서

 

(A1^A1) ^ (A2^...^An) = 0 ^ (A2^...^An) = A2^...^An

 

그러므로 A2 ^ ... ^ An = A1

 

따라서 X1 + X2 + ... Xk의 최댓값은, A1 <= A2 <= ... <= An이라고 했을때..

 

X1,X2,...,Xk로 A2,A3,...An을 선택하고 나머지 Y값은 A1을 선택한다면 된다.

 

#x1^x2^...xk = y1^y2^...y(n-k)일때, x1+x2+..xk의 최댓값
n = int(input())

A = list(map(int,input().split()))

v = A[0]

#양변에 y1^y2^..y(n-k)를 xor한다면 a1^a2^...an = 0이 된다.
for i in range(1,n):
    
    v ^= A[i]

#따라서 모든 원소를 xor했을때 0이 안된다면 불가능하다.
if v != 0:
    
    print(0)

#모든 원소를 xor했을때 0이 된다면..
else:
    
    #a1 <= a2 <= ... an이라고 가정할때..
    #a1^a2^..^an=0에서 a1을 xor하면
    #(a1^a2^..^an)^a1 = 0^a1
    #a2^a3^...an = a1
    #따라서, x집합으로 a2,a3,...,an을 선택하면 최대가 된다.
    print(sum(A) - min(A))