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

· · 题解

前言

由于这题原本是给python代码写的，所以我们用c++写暴力枚举也可以过，但这题标准答案是用 O(n \log n) 时间复杂度的算法来写的，所以在这里我只介绍标准方法。

思路

既然要让时间复杂度降低至 O(n \log n) 级别，那我们可以从位的角度来思考。由于异或运算本身就是建立在位的基础上的，所以我们只需要用一层循环枚举位。由于 1\le a_i\le 2^{20}，所以外层循环复杂度 O(\log a_i) 完全够用。那么内层循环枚举每个数带来的贡献，时间复杂度 O(n)。总时间复杂度 O(n \log a_i)。 \\

实现

大致的框架已经有了，接着我们需要考虑如何将我们的思路用代码实现出来。既然外层循环只是用来枚举位的，那我们可以不用管。重要的是在内层循环中如何统计每个数在这个位中做出的贡献。这个我们得先回看公式：

\sum^n_{i=1}\sum^n_{j=i+1}(a_i\oplus a_j)\times(j-i)

可以看到，如果先不考虑后面的 j-i，那么只有用两个变量统计每位 0 和 1 的个数。然后枚举每个数时，如果这一位是 0，那他得跟这一位为 1 的数异或才能有贡献，所以加上这一位为 1 的数的个数再乘以这一位的权值。反之则加上这一位为 0 的数的个数再乘以这一位的权值。

\\

那么现在问题来了，现在还得乘上 j-i，也就是每一个数他也有一个权值，而且还在不断变化，难道我们还得开一个数组来记录每一个数的权值吗？肯定不可能。观察公式，我们可以发现 i 一直是不变的，只有 j 在增加。那每一次 j 增加 1，j-i 也会增加 1，也就是每一个数的权值也会增加 1，那么我们只需要再新建两个变量来记录每位 0 和 1 的权值，每次只需要加上权值即可。

\\

现在还有一个问题等待着我们解决，那就是每一位上 0 和 1 的权值如何更新。这个其实很简单，因为每一位上 0 和 1 的权值就是每一位上所有数中 0 和 1 的权值之和，那我们已经可以统计每位 0 和 1 的个数，而每次这些数的权值都在加 1。那每一位上 0 和 1 的权值只需要加上相对应的个数就行啦！

示例

输入：

3
1 2 3

转化成二进制就是这样子的：

0 1
1 0
1 1

先来看第一位。此时枚举到第一个数由于此时 0 和 1 的权值都是 0，所以总贡献为 0。然后来到第二个数，由于出现了一个这一位为 1 的数，所以 1 的权值更新为 1。因此这次贡献为当前数值的权值 \times 当前位的权值，也就是 1\times 1=1。 最后到了第三个数，此时 0 的权值更新为 1，因为有了一个当前位为 0 的数。所以当前贡献为当前数值的权值 \times 当前位的权值，也就是 1。

\\

再来看第二位。第一个数依然贡献为 0，所以直接来看第二个数，此时 0 的权值更新为 1，因此这次贡献为当前数值的权值 \times 当前位的权值，也就是 1\times 2=2。最后到了第三个数，此时 0 的权值更新为 2，因为每一次每个数的权值都会加 1。因此这次的贡献为 2\times 2=4。

\\

最后累加总贡献，得数为 8。

代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int maxn=100005;
int n,a[maxn],ans;
int read()
{
    int num=0;
    char s[100];scanf("%s",s);
    for(int i=0;i<strlen(s);i++) num=num*10+s[i]-'0';
    return num;
}
void write(int num)
{
    if(num>9) write(num/10);
    putchar(num%10+'0');
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int k=0;k<=20;k++)
     {
        int cnt[2]={0,0};
        int sum[2]={0,0};
        for(int i=1;i<=n;i++)
         {
            int bit=(a[i]>>k)&1;
            ans+=sum[bit^1]*(1<<k);
            cnt[bit]++;
            sum[0]+=cnt[0];sum[1]+=cnt[1];
         }
     }
    write(ans);
    return 0;
}

代码解释