题解：P12177 [蓝桥杯 2025 省 Python B] 异或和

wenqinghua1001 · 2025-04-18 15:24:42 · 题解

思路

本题要求输出

的值。

首先，暴力使用双重循环，对于 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)