272B.md (1349B)
1 Source: https://codeforces.com/problemset/problem/272/B 2 3 B. Dima and Sequence 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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: 22 23 * *f*(0) = 0; 24 * *f*(2·*x*) = *f*(*x*); 25 * *f*(2·*x* + 1) = *f*(*x*) + 1. 26 27 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. 28 29 Input 30 31 The first line contains integer *n* (1 ≤ *n* ≤ 105). The second line contains *n* positive integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109). 32 33 The numbers in the lines are separated by single spaces. 34 35 Output 36 37 In a single line print the answer to the problem. 38 39 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. 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 1 2 4 48 ``` 49 50 Output 51 52 ``` 53 3 54 ``` 55 56 Input 57 58 ``` 59 3 60 5 3 1 61 ``` 62 63 Output 64 65 ``` 66 1 67 ``` 68 69 Note 70 71 In the first sample any pair (*i*, *j*) will do, so the answer is 3. 72 73 In the second sample only pair (1, 2) will do.