Codeforces Round #167 (Div. 2) B. Dima and Sequence（暴力）

Dima got into number sequences. Now he's got sequence a₁, a₂, ..., 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 < j ≤ n) are there, such that f(a_i) = f(a_j). Help him, count the number of such pairs.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵). The second line contains n positive integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

The numbers in the lines are separated by single spaces.

Output

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.

Sample test(s)

Input

3
1 2 4

Output

Input

3
5 3 1

Output

Note

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.

一直觉得会超时，谁知一次可以AC，看来还是不会分析复杂度。

 1 #include <iostream>
 2 #include <string>
 3 #include <set>
 4 #include <map>
 5 #include <vector>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <cstdio>
10 #include <cstring>
11 #include <algorithm>
12 using namespace std;
13 #define LL long long
14 #define cti const int
15 #define dg(i) cout << "*" << i << endl;
16 
17 int f[1000001];
18 
19 void Init_f()  //先计算一百万以内的f（x），以减少Find函数的递归深度
20 {
21     f[0] = 0;
22     for(int i = 1; i < 1000001; i++)
23         f[i] = f[i/2] + (i & 1);
24 }
25 
26 int Find(int s)
27 {
28     if(s < 1000001) return f[s];
29     return Find(s / 2) + (s & 1);
30 }
31 
32 int main()
33 {
34     int n;
35     LL ans;
36     Init_f();
37     while(scanf("%d", &n) != EOF)
38     {
39         map<int, int> M;
40         int num;
41         ans = 0;
42         while(n--)
43         {
44             scanf("%d", &num);
45             ans = ans + M[Find(num)]++;
46         }
47         printf("%I64d\n", ans);
48     }
49     return 0;
50 }