문제요약
- 길이가 N인 수열이 주어짐(N : 10^6, 숫자 10^9)
- 길이가 1 이상인 부분 수열에서 최대값 x 최소값
- 부분 수열들의 최대값 x 최소값 들의 XOR
접근법
- 다 해볼수는 없음 : 부분수열의 경우의 수 = 2^N
- 최대값, 최소값을 정해놓는다면?
- 10(최대값), ........, 2(최소값) 의 수열일때 사이에 들어가는 숫자는 정해져있음
- 사이에 들어갈 수 있는 숫자가 K개라고 할때 10(최대값), 2(최소값)인 수열의 개수는 2^K개
- 수열의 길이가 1일때 => 수열의 개수=1개, XOR=최대x최소
- 수열의 길이가 2일때 => 수열의 개수=1개, XOR=최대x최소
- 수열의 길이가 3이상일때 => 수열의 개수=2^K개, XOR=0 (왜냐면 최대x최소를 짝수번만큼 XOR)
- N을 내림차순(또는 올림차순)으로 정렬 후, 각각의 숫자들을 제곱한 것과 인접한 숫자를 곱한것들을 서로 XOR 하면 됨
newbieski