自动搬运

查看原文

来自洛谷，原作者为

	wenqinghua1001 ZYX0716 是指以(0,0,0)为原点，Z轴是7，Y轴是1，X轴是6的点||离线||估值：100+51+71+46+30=298||欢迎互关，私信，可小号双关 ||不开long long见祖宗，开了long long爆内存||喜欢出题的六年级蒟蒻

搬运于2025-08-24 23:13:27，当前版本为作者最后更新于2025-04-18 15:24:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

本题要求输出

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i) $$

的值。

首先，暴力使用双重循环，对于 $100\%$ 的数据，$1 \le n \le 10^5$，$n^2$ 最大是 $10^{10}$，定会超时，排除 $O(n^2)$ 做法。那么肯定要进行优化。

首先，数据最大值的二进制有多少位，外循环就遍历多少次。$1 \le a_i \le 2^{20}$，外循环最多遍历 $20$ 次。内循环从最小位开始，拿出每个数据二进制的第 $i$ 位，只有当两个数一个为 $0$，一个为 $1$ 时，才会对最后结果产生贡献。因为按位异或的原理全是真或全是假为 $0$，一假一真为 $1$。

就拿第二组样例说，第 $i$ 层内循环求出所有从右向左第 $i$ 个数是 $1$ 和 $0$ 的两个数，位权和位置差的积，例示：

以此推出第三层、第四层，最终答案是 $6+16+32+64=118$。

Python 代码

AC 记录

import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(20):
    xiabiaohe_0 = 0 
    xiabiaohe_1 = 0
    geshu_0 = 0 
    geshu_1 = 0
    for j in range(n):
        q = (a[j] >> i) & 1
        if q==1: # 此位为 1。
            ans += (j * xiabiaohe_0 - geshu_0) * (1 << i)
            xiabiaohe_1 += 1
            geshu_1 += j
        else: # 此位为 0。
            ans += (j * xiabiaohe_1 - geshu_1) * (1 << i)
            xiabiaohe_0 += 1
            geshu_0 += j
print(ans)