부분집합 합의 XOR

시간 제한1초메모리 제한512 MB

요약

n개의 정수가 주어질 때, 2^n개 부분집합의 합을 모두 XOR한 값을 구한다.

문제

정수 $n$ 개 $A_1, A_2, \dots, A_n$ 이 주어진다. $N = \{1, 2, \dots, n\}$ 이라고 하자.

$N$ 의 부분집합 $I$ 에 대해 $S_I$ 를 다음과 같이 정의한다.

$S_I = \sum_{k \in I} A_k$

즉 $I$ 에 속한 첨자 $k$ 의 $A_k$ 를 모두 더한 값이다. 공집합의 합은 0이고, $N$ 자신도 부분집합으로 센다. 그러므로 $S_I$ 는 모두 $2^n$ 개다.

이 $2^n$ 개의 값을 전부 비트 단위 배타적 논리합(XOR)한 결과를 $X$ 라고 하자.

$X = \bigoplus_{I \subseteq N} S_I$

$X$ 를 구하라.

첫째 줄에 $n$ 이 주어진다. ( $1 \le n \le 30$ )

둘째 줄에 $n$ 개의 정수 $A_1, A_2, \dots, A_n$ 이 공백으로 구분되어 주어진다. ( $0 \le A_i < 2^{30}$ )

첫째 줄에 $X$ 를 출력한다.