#DP #Solved #Codeforces

B. Dima and Sequence.cpp

//http://codeforces.com/contest/272/problem/B
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int OO = 1e4;
int cache[(int)1e6+5];
int a[(int)1e5+5];
int mem[1000];
int n;
int calc(int x) {
    if(x == 0)
        return 0;

    if(x < (int) 1e6) {
        int &ret = cache[x];
        if(ret != -1)
            return ret;

        if(x&1)
            ret = 1+calc(x>>1);
        else
            ret = calc(x>>1);
        return ret;
    } else {
        int ret;

        if(x&1)
            ret = 1+calc(x>>1);
        else
            ret = calc(x>>1);
        return ret;
    }


}

int main() {
    cin>>n;
    ll sum = 0;
    clr(cache, -1);
    clr(mem, 0);
    ll x;
    lp(i, n) {
        cin>>a[i];
        x = calc(a[i]);
        mem[x]++;
    }
    lp(i, 1000) {
        if(mem[i] > 1) {
            if(mem[i]&1) {
                x = (mem[i]-1)/2;
                x = x*mem[i];
            }else {
                x = mem[i]/2;
                x = x*(mem[i]-1);
            }
            sum+= x;
        }
    }

    cout << sum << endl;

    return 0;
}