P9236 [蓝桥杯 2023 省 A] 异或和之和 题解

· · 题解

P9236 [蓝桥杯 2023 省 A] 异或和之和

首先，异或有一个重要的性质：

a\oplus b \oplus b=a

因为 b 的二进制位一定与自己一样，根据异或的定义，得出 b\oplus b=0，进而推出这个式子。

有了这个式子，区间异或和就可以像前缀和一样处理了。

我们可以求出每一项的前缀异或和，记作 q_i，根据上面那条性质，可以仿照前缀和的形式写出区间 [l,r] 的异或和（记作 S_{l,r}）的 O(1) 求法式子：（下标均从 1 开始）

S_{l,r}=p_r\oplus p_{l-1}

所以，我们用这个式子来求解每个区间的异或和，可以把每个子段的异或和的和转变为下面式子：（这里 p_0 默认取 0 值，因为还需要查询类似 [1,i] 这种区间的值）

\sum_{i=1}^{n}\sum_{j=0}^{i-1}p_i\oplus p_j

但这个做法的复杂度是 O(n^2)，不够通过本题的数据范围，所以我们还需要在这个基础上继续优化。

在这个式子中，我们可以观察到，对于每一对 i,j 不相等的有序数对 (i,j)，p_i,p_j 都恰好只互相异或了一次。所以，问题又转化为了 n 个数，其中两两异或的求和。

这个时候会发现推式子已经到达尽头了，再怎么推也不会得到新的结论。必须从其他方面考虑问题，比如异或运算的计算原理的方面。可以考虑把每个数按二进制拆分，在每一位上统计该位的贡献。由于最后是两两异或的求和，所以二进制拆分后打乱不会影响结果。

由于异或的运算法则是如果同位数字不同，那么运算结果的这一位为 1。我们知道，只有二进制位为 1 对最终的结果（加和）有贡献，所以我们可以统计二进制结果为 1 的情况。

对于每一个 p_i，我们将其按位拆分，并将结果存入计数数组 w_{i,j} 中。其中 i 表示第 i 个二进制位，j 表示这一位上为 j（只能为 0 或 1），w_{i,j} 表示在所有数中，第 i 个二进制位上为 j 的有 w_{i,j} 个。

由于这些数中必定两两异或，所以可以直接用乘法原理，求出该位最终为 1 的个数，最后乘上该位的权值就可以了。所以最后的答案为：（公式中 i 的范围上界到 20 是因为题目中说 A_i\le2^{20}，最多只有 21 个二进制位）

\sum_{i=0}^{20}w_{i,0}\times w_{i,1}\times 2^i

时间复杂度 O(n)，可以通过本题。

#include <bits/stdc++.h>
using namespace std;
long long n,a[100010],q[100010],w[100010][2],ans=0;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)q[i]=q[i-1]^a[i];
    for(int i=0;i<=n;i++)
        for(int j=20;j>=0;j--)
            w[j][(q[i]>>j)&1]++;
    for(int i=0;i<=20;i++)
        ans+=w[i][0]*w[i][1]*(1<<i);
    printf("%lld",ans);
    return 0;
}

AC记录