← 返回题目列表

Codeforces · 272/B

B. 迪马和序列

中文机器翻译题面 查看原题

迪玛陷入了数字序列。现在他得到了由 n 个正整数组成的序列 a1, a2, ..., an。此外,Dima 有一个函数 f(x),可以用以下递归式定义:

- f(0) = 0;
- f(2·x) = f(x);
- f(2·x + 1) = f(x) + 1。

Dima 想知道,有多少对索引 (i, j) (1 ≤ i < j ≤ n),使得 f(ai) = f(aj)。帮他数一下这样的对的数量。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含 n 个正整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。

行中的数字由单个空格分隔。

输出

在一行中打印问题的答案。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3
1 2 4

输出 #1

3

输入 #2

3
5 3 1

输出 #2

1

注意

在第一个样本中,任何对 (i, j) 都可以,所以答案是 3。

在第二个示例中,只有 (1, 2) 对可以。