13339번 - XOR 수열

수열 A와 정수 N이 주어진다. N은 2의 제곱꼴이고, A의 각 원소는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다.

0보다 크거나 같고, N-1보다 작거나 같은 정수 B를 골라서, 새로운 수열 C를 만들 수 있다. 각각의 i에 대해서, C_i = A_i xor B로 C를 만든다.

그 다음, C에서 i < j 이면서 C_i < C_j인 (i, j)쌍의 개수를 센다.

B를 적절히 골라서 이러한 쌍의 개수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 N (2 ≤ N ≤ 2³⁰), 둘째 줄에 수열 A의 크기 M (2 ≤ M ≤ 131072), 셋째 줄에 수열 A의 각 원소 A_i가 주어진다.

i < j 이면서 C_i < C_j인 (i, j)쌍의 개수의 최댓값을 출력한다.

예제 1의 경우에 B=3을 고르면, C = [0, 1, 2, 3, 0, 1]이 된다. 이때, i < j이면서 C_i < C_j인 쌍의 개수는 8개이다.