codeforce 272B Dima and Sequence

风骨散人Chiam

发布于 2020-10-28 10:18:11

3330

发布于 2020-10-28 10:18:11

文章被收录于专栏：CSDN旧文

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/30 ，如有侵权请联系 cloudcommunity@tencent.com 删除

contains