Dima and Sequence

题意翻译

### 题目描述 Dima被数列吸引住了。现在他有一个数列$a_1, a_2, ..., a_n$，由$n$个正整数组成。Dima还有一个函数$f(x)$，其定义如下： - $f(0) = 0$； - $f(2·x) = f(x)$； - $f(2·x + 1) = f(x) + 1$ Dima想知道有多少对数$(i, j)(1 \leq i < j \leq n)$满足$f(a_i) = f(a_j)$。请帮助Dima求出这种对数的个数。 ### 输入格式 第一行包含一个整数$n (1 \leq n \leq 10^5)$。 第二行包含$n$个被单个空格隔开的正整数$a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)$。 ### 输出格式 一个数，代表如上所述的对数的个数。 温馨小提示：在C++不要使用`%lld`来读写64位的整数。推荐使用输入输出流或`%l64d`。

题目描述

Dima got into number sequences. Now he's got sequence $ a_{1},a_{2},...,a_{n} $ , consisting of $ n $ positive integers. Also, Dima has got a function $ f(x) $ , which can be defined with the following recurrence: - $ f(0)=0 $ ; - $ f(2·x)=f(x) $ ; - $ f(2·x+1)=f(x)+1 $ . Dima wonders, how many pairs of indexes $ (i,j) $ $ (1<=i&lt;j<=n) $ are there, such that $ f(a_{i})=f(a_{j}) $ . Help him, count the number of such pairs.

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ . The second line contains $ n $ positive integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{9}) $ . The numbers in the lines are separated by single spaces.

输出格式

In a single line print the answer to the problem. Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

3
1 2 4

输出样例 #1

3

输入样例 #2

3
5 3 1

输出样例 #2

1

说明

In the first sample any pair $ (i,j) $ will do, so the answer is $ 3 $ . In the second sample only pair $ (1,2) $ will do.