33102번 - Counting Pairs 다국어

문제

Consider the binary operator $\oplus_b(x, y)$ that is defined for $b \in \{2, 4\}$ as follows. First, convert both $x$ and $y$ into base $b$. Then, for each corresponding digit pair, the resulting digit can be calculated by adding the digit pair modulo $b$. Finally, convert the result back to base ten. Notice that $\oplus_2$ is the bitwise XOR operator.

For instance, $\oplus_4(18, 7) = 21$ can be calculated as follows. The base four representations of 18ドル$ and 7ドル$ are $(102)_4$ and $(013)_4,ドル respectively. After the addition for each digit pair, the result is $(111)_4,ドル or 21ドル$ in base ten.

You are given a list of $N$ integers, $A_1, A_2, \dots , A_N$.

Determine the number of pairs $(i, j)$ such that 1ドル ≤ i < j ≤ N$ and $\oplus_2(A_i , A_j ) = \oplus_4(A_i , A_j )$.

입력

The first line consists of an integer $N$ (2ドル ≤ N ≤ 200,円 000$).

The next line consists of $N$ integers $A_i$ (0ドル ≤ A_i ≤ 10^{12}$).

출력

Output a single integer representing the number of pairs $(i, j)$ such that 1ドル ≤ i < j ≤ N$ and $\oplus_2(A_i , A_j ) = \oplus_4(A_i , A_j )$.

제한

힌트