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
代码语言：javascript复制3
1 2 4output
代码语言：javascript复制3input
代码语言：javascript复制3
5 3 1output
代码语言：javascript复制1Note
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条，找到规律。
偶数找规律，计数找祖宗。
代码语言：javascript复制#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;
}
