1000ms

Difficulty: 2

所属公司 : 饿了么

时间 :2025年4月12日(算法方向)

算法与标签>暴力枚举

会员专享

请先，开通会员，可解锁完整内容。

开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员后可解锁完整内容。

开通会员

解题思路

值域压缩： $a_i\le 1000$ ，先统计每个值的出现次数 $cnt[v]$ 。
枚举值对：枚举 $1\le u\le v\le 1000$ 。令 $w=u\oplus v$ ，判断 $u,v,w$ 能否构成非退化三角形，即 $u+v>w,\quad u+w>v,\quad v+w>u.$
贡献计算：
- 若 $u<v$ ，贡献 $cnt[u]\times cnt[v]$ ；
- 若 $u=v$ ，贡献 $cnt[u]\times(cnt[u]-1)/2$ 。
累加即为下标对数量。

题目内容

给定长度为 $n$ 的正整数数组 $a$ 。称一对下标 $(i,j)$ （ $1 \le i < j \le n$ ）是可行对，当且仅当 $a_i$ 、 $a_j$ 与 $a_i \oplus a_j$ 可以作为三条边构成一个非退化三角形。其中 $\oplus$ 表示按位异或。

求可行对的数量。

数组长度 $n$ 满足 $1 \le n \le 10^5$ 。数组元素满足 $1 \le a_i \le 1000$ 。

输入描述

第一行包含一个正整数 $n$ ，表示数组长度。