codeforce 272B Dima and Sequence

B. Dima and Sequence

Dima got into number sequences. Now he's got sequence a1, a2, ..., an, 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(ai) = f(aj). Help him, count the number of such pairs.

Input

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

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 %I64dspecifier.

Examples

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.

打表100条，找到规律。

偶数找规律，计数找祖宗。

#include<iostream>

#include<queue>

#include<algorithm>

#include<set>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<bitset>

#include<cstdio>

#include<cstring>

//---------------------------------Sexy operation--------------------------//

#define cini(n) scanf("%d",&n)

#define cinl(n) scanf("%lld",&n)

#define cinc(n) scanf("%c",&n)

#define cins(s) scanf("%s",s)

#define coui(n) printf("%d",n)

#define couc(n) printf("%c",n)

#define coul(n) printf("%lld",n)

#define debug(n) printf("%d_________________________________\n",n);

#define speed ios_base::sync_with_stdio(0)

#define file  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

//-------------------------------Actual option------------------------------//

#define rep(i,a,n) for(int i=a;i<=n;i++)

#define per(i,n,a) for(int i=n;i>=a;i--)

#define Swap(a,b) a^=b^=a^=b

#define Max(a,b) (a>b?a:b)

#define Min(a,b) a<b?a:b

#define mem(n,x) memset(n,x,sizeof(n))

#define mp(a,b) make_pair(a,b)

#define pb(n)  push_back(n)

//--------------------------------constant----------------------------------//

#define INF  0x3f3f3f3f

#define maxn  10000000

#define esp  1e-9

using namespace std;

typedef pair<int,int>PII;

typedef pair<string,int>PSI;

typedef  long long ll;

//___________________________Dividing Line__________________________________//

long long a[40]= {0};

int main()

{

    int n,x;

    cini(n);

    while(n--)

    {

        int sum=0;

        cini(x);

        while(x){

            if(x&1){

                sum++;

                x=(x-1)/2;

            }

            else  x/=2;

        }

        a[sum]++;

    }

    long long ans=0;

    for(int i=0; i<40; i++)

        ans+=a[i]*(a[i]-1)/2;

    cout<<ans<<endl;

    return 0;

}

巴特西

codeforce 272B Dima and Sequence

最新文章

热门文章