부분 수열 XOR 합

면접 대비

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

요약

수열의 모든 연속 부분 배열에 대해 XOR 값을 구해 각 값이 몇 번 나타나는지 세고, 가장 자주 나온 값과 그 횟수를 출력한다. 최빈값이 여러 개면 가장 작은 값을 고른다.

난이도: 보통10점 중 6점
유형: 누적 합, 비트 연산, 해시맵, 배열
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 수열 $A = a_0, a_1, \dots, a_{n-1}$ 이 있다. $A$ 의 부분 수열은 $0 \le i \le j < n$ 을 만족하는 두 인덱스 $i$ , $j$ 로 정해지는 연속한 구간 $a_i, a_{i+1}, \dots, a_{j-1}, a_j$ 이다.

예를 들어 $n = 3$ 이면 부분 수열은 다음 6개이다.

$a_0$
$a_1$
$a_2$
$a_0, a_1$
$a_1, a_2$
$a_0, a_1, a_2$

부분 수열의 XOR 합은 그 부분 수열에 들어 있는 모든 수를 XOR한 값이다. 부분 수열은 모두 $n(n+1)/2$ 개이므로 XOR 합도 $n(n+1)/2$ 개 나온다. 이 값 중에서 가장 많이 등장한 값과 그 등장 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 $A$ 의 크기 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

둘째 줄에 $a_0, a_1, \dots, a_{n-1}$ 이 공백으로 구분되어 주어진다 ( $1 \le a_i < 2^{16}$ ).

출력

첫째 줄에 두 정수를 공백으로 구분해 출력한다. 첫 번째 정수는 XOR 합으로 가장 많이 등장한 값이고, 두 번째 정수는 그 값이 등장한 횟수이다. 가장 많이 등장한 값이 여러 개면 그중 가장 작은 값을 출력한다.

예제3

예제 1
입력
```
4
2 1 1 3
```
예상 출력
```
1 3
```
예제 2
입력
```
1
1
```
예상 출력
```
1 1
```
예제 3
입력
```
2
1 1
```
예상 출력
```
1 2
```