CodeForces-1323D Present

传送门：CodeForces-1323D

题目描述

每两两组合形成一个数，求这些数的异或和

输入描述

The first line contains $a$ single integer $n$ $(2≤n≤400000)$ — the number of integers in the array.

The second line contains integers $a_1,a_2,…,a_n$ $(1≤a_i≤10^7).$

输出描述

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

思路分析

一般这种二进制的题，都需要对分别每一位计算贡献
对于第$i$位，大于这一位的跟答案没关系，所以可以创建一个新数组$b$为原数组第$i$位以下的部分
只有$b_i+b_j$的第i位是1的时候才对答案有贡献
即在$[2^i,2^{i+1}-1]\bigcup[2^{i+1}+2^i,2^{i+2}-1]$的时候对答案有影响
可以固定$i$然后二分查找符合条件的区间
如果数量为奇数，那么这一位的答案是$1$

样例输入

2
1 2

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

int a[N],b[N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    int ans=0;
    for(int i=0; i<26; i++) {
        int p=(1<<(i+1))-1;
        for(int j=0; j<n; j++)
            b[j]=a[j]&p;
        sort(b,b+n);
        p=(1<<i);
        ll sum=0;
        for(int j=0; j<n; j++) {
            int t1=lower_bound(b+j+1,b+n,p-b[j])-b;
            int t2=upper_bound(b+j+1,b+n,(p<<1)-1-b[j])-b;
            sum+=t2-t1;
            t1=lower_bound(b+j+1,b+n,(p<<1)+p-b[j])-b;
            t2=upper_bound(b+j+1,b+n,(p<<2)-1-b[j])-b;
            sum+=t2-t1;
        }
        if(sum&1)ans+=p;
    }
    cout<<ans<<endl;



    return 0;
}