30961번 - 최솟값, 최댓값
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 443 | 299 | 244 | 67.778% |
문제
수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$인 수열 $A$가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라.
입력
첫 번째 줄에 $N$이 주어진다. $(1 \le N \le 10^6)$
두 번째 줄에 수열 $A$를 이루는 정수 $N$개가 순서대로 주어진다. $(0 \le A_i \le 10^9)$
출력
첫 번째 줄에 문제의 답을 출력한다.
예제 입력 1
3 2 3 1
예제 출력 1
8
힌트
부분수열은 수열에서 순서를 유지하며 $1$개 이상 $N$개 이하의 원소를 골라 만들 수 있는 수열을 의미한다. 연속할 필요는 없다.
XOR은 두 수를 동일한 길이의 이진수로 나타내었을 때 동일한 길이의 이진수를 반환하는 연산이다. 반환값의 $k$번째 숫자는 두 이진수 입력의 $k$번째 위치의 숫자가 같다면 $0$, 다르다면 $1$이 된다.