쌍의 개수 세기

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

요약

두 수가 짝수 번째 비트(0, 2, 4, ...)에서 동시에 1인 적이 없는 쌍의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 비트 연산, 동적 계획법
정답자: 아직 제출이 없습니다

문제

다음과 같이 이항 연산자 $\oplus_b(x, y)$ 를 $b \in \{2, 4\}$ 에 대해 정의한다. 먼저 $x$ 와 $y$ 를 각각 $b$ 진법으로 변환한다. 그다음 대응하는 자릿수 쌍마다 두 자릿수를 더한 값을 $b$ 로 나눈 나머지를 결과의 자릿수로 삼는다. 마지막으로 결과를 10진법으로 바꾼다. $\oplus_2$ 는 비트 단위 XOR 연산이다.

예를 들어 $\oplus_4(18, 7) = 21$ 이다. 18과 7의 4진법 표현은 각각 $(102)_4$ 와 $(013)_4$ 이다. 자릿수끼리 더하면 $(111)_4$ 가 되고, 이는 10진법으로 21이다.

정수 $A_1, A_2, \dots, A_N$ 이 주어진다. $1 \le i < j \le N$ 을 만족하는 쌍 $(i, j)$ 가운데 $\oplus_2(A_i, A_j) = \oplus_4(A_i, A_j)$ 를 만족하는 쌍의 개수를 구한다.

입력

첫 줄에 정수 $N$ ( $2 \le N \le 200000$ )이 주어진다. 둘째 줄에 정수 $A_1, A_2, \dots, A_N$ ( $0 \le A_i \le 10^{12}$ )이 주어진다.

출력

조건을 만족하는 쌍 $(i, j)$ 의 개수를 한 줄에 출력한다. 단, $1 \le i < j \le N$ 이고 $\oplus_2(A_i, A_j) = \oplus_4(A_i, A_j)$ 이다.

예제4

예제 1
입력
```
5
2 2 0 1 3
```
예상 출력
```
9
```
예제 2
입력
```
2
17 13
```
예상 출력
```
0
```
예제 3
입력
```
10
13 7 29 4 18 0 4 21 12 20
```
예상 출력
```
14
```
예제 4
입력
```
10
0 0 0 0 0 0 0 0 0 0
```
예상 출력
```
45
```