D. Present

Link: D. Present

Description

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

Here is a bitwise XOR operation (i.e. x ^ y in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

Input
The first line contains a single integer n () — the number of integers in the array.

The second line contains integers ().

Output
Print a single integer — xor of all pairwise sums of integers in the given array.

Examples
input
2
1 2
output
3
input
3
1 2 3
output
2
Note
In the first sample case there is only one sum 1+2=3.

In the second sample case there are three sums: 1+2=3, 1+3=4, 2+3=5. In binary they are represented as , thus the answer is 2.

()is the bitwise xor operation. To define , consider binary representations of integers x and y. We put the i-th bit of the result to be 1 when exactly one of the i-th bits of x and y is 1. Otherwise, the i-th bit of the result is put to be 0.For example,

Problem solving

这道题的意思是给你一个序列，让你求序列中每个数两两之和的异或和。暴力是肯定不行的。
看到异或，我们首先就应该往按位运算的方向想。假设我们现在想知道答案中二进制位第k位的值。我们可以发现，对这一位有影响的就是原序列中每个数的二进制位中的第0位到第k位。所以我们可以将序列中的每个数对取模。这样取模之后，假设任意两数之和为m，那么当m处于或者时，第k位为1。所以我们可以统计出来两个数的和第k位为1的对数。因为他们是异或，所以如果对数是奇数，那么答案中的第k位就是1，否则就是0.统计对数的时候我们可以二分查找，这样时间复杂度是

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
int a[maxn],b[maxn];
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    int n;ll ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)    cin>>a[i];
    for(int k=0;k<30;k++){//因为最大也就是2e6，所以30位二进制位是足够的
        int mod=1<<(k+1);
        for(int i=1;i<=n;i++)    b[i]=a[i]%mod;
        sort(b+1,b+n+1);
        ll mid=0;
        for(int i=1;i<=n;i++){
            mid+=upper_bound(b+i+1,b+n+1,(1<<(k+1))-1-b[i])-lower_bound(b+i+1,b+n+1,(1<<k)-b[i]);//为了避免重复的对数，每次从第i位往后找
            mid+=upper_bound(b+i+1,b+n+1,(1<<(k+2))-b[i])-lower_bound(b+i+1,b+n+1,(1<<k)+(1<<(k+1))-b[i]);//注意upper和lower的使用
        }
        if(mid&1)    ans+=(1<<k);//如果第k位是1的对数有奇数个，那么答案中的第k位就是1，即(1<<k)($$2^k$$)
    }
    cout<<ans<<endl;
    return 0;
}
赏