题目描述

难度分:$2207$

输入$n(1 \leq n \leq 2 \times 10^5)$和两个长为$n$的数组$a$，$b$，元素范围在$[0,2^{28})$。

从$a$中选一个数$a[i]$，从$b$中选一个数$b[j]$，相加得到$a[i]+b[j]$，这一共有$n^2$个数字。

输出这$n^2$个数的异或和。

输入样例$1$

2
1 2
3 4

输出样例$1$

2

输入样例$2$

6
4 6 0 0 3 3
0 5 6 5 0 3

输出样例$2$

8

输入样例$3$

5
1 2 3 4 5
1 2 3 4 5

输出样例$3$

2

输入样例$4$

1
0
0

输出样例$4$

0

算法

拆位+二分

一般这样的位运算题目都要逐位考虑。

若$a_i+b_j$的第$k$位是$1$，则$a_i+b_j$有可能是以下两种情况：

1. 从1000...000到1111...111（每个二进制数是$[0,k]$位），转换成十进制就是$[2^k,2^{k+1}-1]$。
2. 如果进位了的话就是从1100...000到1111...111（每个二进制数是$[0,k+1]$位），转换成十进制就是$[2^{k+1}+2^k,2^{k+2}-1]=[3 \times 2^k,2^{k+2}-1]$。

此时如果枚举$a_i$，问题就转化为有多少个$b[j]$在$[2^k-a_i,2^{k+1}-1-a_i]$或$[3 \times 2^k-a_i,2^{k+2}-1-a_i]$范围内，把$b$排序后，二分查找一下就可以确定出来。

根据异或的性质，只要这个数量是奇数，就能保证异或操作之后第$k$位是$1$。

复杂度分析

时间复杂度

遍历总的位数是$29$位，设其为$A$。对于每一位，首先需要对$b$进行$O(nlog_2n)$的排序，之后才能在遍历$a_i$的过程中，通过二分查找确定符合题意的$b_j$。而遍历$a_i$的时间复杂度是$O(n)$，二分查找的时间复杂度是$O(log_2n)$，因此时间复杂度同样是$O(nlog_2n)$。因此，算法整体的时间复杂度是$O(Anlog_2n)$。

空间复杂度

在考虑每一位$k$的结果时，会先将比$k$高的位清空，避免高位的影响。因此，需要对$a$和$b$进行拷贝，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, a[N], b[N], c[N], d[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    int ans = 0;
    for(int k = 0; k <= 28; k++) {
        // 把第k位以上的截断
        for(int i = 1; i <= n; i++) {
            c[i] = a[i]&((1<<(k + 1)) - 1);
            d[i] = b[i]&((1<<(k + 1)) - 1);
        }
        sort(d + 1, d + n + 1);
        LL cnt = 0;
        for(int i = 1; i <= n; i++) {
            int l = (1<<k) - c[i], r = (1<<(k + 1)) - 1 - c[i];
            cnt += upper_bound(d + 1, d + 1 + n, r) - lower_bound(d + 1, d + 1 + n, l);
            l = 3*(1<<k) - c[i], r = (1<<(k + 2)) - 1 - c[i];
            cnt += upper_bound(d + 1, d + 1 + n, r) - lower_bound(d + 1, d + 1 + n, l);
        }
        if(cnt&1) ans |= 1<<k;
    }
    printf("%d\n", ans);
    return 0;
}