互补数对(Complementary Pairs)

题目描述

给定 n 个正整数 a₁, a₂, …, aₙ，求其中有多少对数字 {x, y} 满足 x & y = 0，且 x ≤ y。

其中 & 表示按位与操作，例如 6 & 3 = (110)₂ & (011)₂ = (010)₂ = 2。

输入格式

• 第一行：单个整数 n。
• 第二行：n 个整数，a₁, a₂, …, aₙ

输出格式

• 单个整数：表示按位与结果为 0 的数对。

数据范围

• 对于 50% 的数据，1 ≤ n ≤ 10⁴
• 对于 100% 的数据，1 ≤ n ≤ 10⁶，1 ≤ aᵢ ≤ 10⁶

样例输入 #1

4
2 5 4 27

样例输出 #1

3

说明: (2,5) (2,4) (4,27)

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布