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

lcfollower · 2025-04-13 15:36:21 · 题解

首先暴力 \mathcal O(n^2) 包 TLE。

观察数据，1\le a_i\le 2^{20}，如果时间和值域无关可以设 a_i 小于等于一个极大值，猜测时间复杂度与值域有关。

异或的题一般两种方法：二进制逐位处理和字典树，这里用第一种方法。

明显 0\oplus 1 = 1，1\oplus 0 = 1，于是考虑分别处理当前数的二进制在当前位置下为 0 和 1 的情况。

设当前处理到第 i 位（从右往左从 0 开始），处理的数是 a_j。

• 如果 a_j 的第 i 位是 0，则对答案贡献为 bit \times (j \times sum1 - p1)，其中 bit 为第 i 个二进制位的权值（即 2^i），sum1 为前面的数第 i 位为 1 的个数，p1 为前面的数第 i 位为 1 的数的 j' 的和。这样我们可以实现 \sum (j - j') 的计算（乘法具有结合律）。

• 如果 a_j 的第 i 位是 1，则对答案的贡献为 bit\times (j \times sum0 - p0)，sum0，p0 的解释如上。

这样我们就能完成此题，时间复杂度为 \mathcal O(n\log a)。

以下为 python 代码，由 https://www.deepseek.com 把 C++ 代码改成 python 语言：

import sys

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    ans = 0
    bit = 1

    for i in range(21):
        p0 = 0
        p1 = 0
        sum0 = 0
        sum1 = 0

        for j in range(n):
            current = a[j]
            if (current >> i) & 1:
                ans += bit * ((j + 1) * sum0 - p0)
                p1 += j + 1
                sum1 += 1
            else:
                ans += bit * ((j + 1) * sum1 - p1)
                p0 += j + 1
                sum0 += 1

        bit <<= 1

    print(ans)

if __name__ == "__main__":
    main()

附加 C++ 代码，但是通过计算会发现：

十年 OI 一场空，不开 __int128 见祖宗。

#include<bits/stdc++.h>

#define int __int128
#define up(i,x,y) for(int i=x;i<=y;i++)

using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}

const int N = 1e5 + 10;
int n ,a[N] ,ans ,pre[N];

signed main(){
  n = read ();
  up (i ,1 ,n) a[i] = read () ;
  int bit = 1;
  up (i ,0 ,20){
    int p0 = 0 ,p1 = 0 ,sum0 = 0 ,sum1 = 0;
    up (j ,1 ,n){
      if ((a[j] >> i) & 1) ans += bit * (j * sum0 - p0) ,p1 += j ,sum1 ++;
      else ans += bit * (j * sum1 - p1) ,p0 += j ,sum0 ++;
    }
    bit <<= 1;
  } writeln (ans);
  return 0;
}