题目描述

我们定义一种特殊的神秘异或操作 $\oplus_m$，规则如下：

对于两个数 $a$ 和 $b$，首先计算它们的常规异或结果 $c=a⊕b$。然后按以下方式处理 $c$ 的二进制表示：

1. 从最低有效位到最高有效位扫描c的二进制表示
2. 初始化一个计数器 $count=0$
3. 对于每一位：
   • 如果该位是 $1$：
     • 将 $count$ 加 $1$
     • 如果 $count$ 是奇数，保留该位
     • 如果 $count$ 是偶数，清除该位（设为 0）
   • 如果该位是 0，保持不变

示例：$(101001)_2 ⊕m (10010)_2 = (101001)_2$

给定一个长度为 $N$ 的数组 $A$，计算所有无序对 $(i,j)$（其中 $i=j$）$Ai$ 和 $Aj$ 的神秘异或结果之和。 形式化地，其可以被表示为$\sum_{i=1}^{N} \sum_{j=i+1}^{N} A_i \oplus_m A_j$。

输入格式

第一行包含一个整数 $N (2⩽N⩽10^5)$。

第二行包含 $N$ 个整数 $A_i (0⩽A_i⩽10^8)$。

输出格式

输出一个整数，表示所有无序对的神秘异或结果之和。

3
5 3 9

8

解释 #1

$5 \oplus_m 3=2$

$5 \oplus_m 9=4$

$3 \oplus_m 9=2$

所以答案等于 $4+2+2=8$