自动搬运

查看原文

来自洛谷，原作者为

	Nangu 加 训

搬运于2025-08-24 23:09:09，当前版本为作者最后更新于2025-02-01 18:37:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们按位计算答案。

设当前枚举到了第 $k$ 位，下文计 $b_i$ 表示 $a_i$ 在第 $k$ 位的值，$c_i$ 表示 $a_i$ 前 $k-1$ 位的值（当 $k=1$ 时 $c_i=0$）。

$a_i+a_j$ 的第 $k$ 位为 $1$，当且仅当 $ [b_i=1] \operatorname{xor} [b_j=1] \operatorname{xor} [c_i+c_j\ge 2^k]=1$（其实就是一个不考虑进位的加法），易得答案的第 $k$ 位为 $$\displaystyle\bigoplus _{1\le i\le j\le n}[b_i=1] \operatorname{xor} [b_j=1] \operatorname{xor} [c_i+c_j\ge 2^k]$$。

我们讲这三个贡献分开算，前两个是容易的，做第三个时，考虑讲 $c_i$ 排序，然后用双指针维护。排序的复杂度为 $O(\log n)$，再加上枚举 $k$ 的复杂度，总复杂度为 $O(n\log n \log maxa)$，可以拿到五十二分。

瓶颈在于排序，我们考虑用类似于基数排序的方法来实现这个排序，在从小到大枚举 $k$ 时，若 $c_i=1$，就将 $i$ 放到序列的后面，若 $c_i=0$，就将 $i$ 放到序列的前面，相等的 $c$ 之间的相对位置不改变，这样总复杂度就由 $O(n\log n \log maxa)$ 降为 $O(n\log maxa)$ 了。

代码：

#include<bits/stdc++.h>
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
#define print(a, len) cout<<#a<<"= "; rep(i, 0, len-1) cout<<(a)[i]<<' '; cout<<endl;
using namespace std;
namespace DEBUG{
	template<class T> void _debug(const char *s, T x){cout<<s<<'='<<x<<endl;}
	template<class T, class... Nxt> void _debug(const char *s, T x, Nxt... nxt){
		while(*s!=',') cout<<*s++;
		cout<<'='<<x<<',';
		_debug(s+1, nxt...);
	}
	template<class T> ostream& operator<<(ostream& c, vector<T> x){
		c<<'[';
		for(auto v:x) c<<v<<", ";
		return c<<']';
	}
	#ifdef ck
	#define debug(...) 0
	#else
	#define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
	#endif
} using namespace DEBUG;
const int N=5e5+7;
int n, a[N], b[N], c[N], d[N], c1, c2, ans;
int buc[N];
inline bool bit(int s, int i){return s>>i&1;}
inline int mod(int s, int k){return s&((1<<k)-1);}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	rep(i, 1, n) cin>>a[i];
	rep(k, 0, 30){
		auto bit=[&](int i){return a[i]>>k&1;};
		auto mod=[&](int i){return a[i]&((1<<k)-1);};
		bool res=0;
		if(n+1&1) rep(i, 1, n) res^=bit(i);
		if(k){
			c1=c2=0;
			rep(i, 1, n) if(mod(i)<1<<k-1) b[++c1]=i; else c[++c2]=i;
			rep(i, 1, c1) d[i]=a[b[i]];
			rep(i, 1, c2) d[c1+i]=a[c[i]];
			rep(i, 1, n) a[i]=d[i];
			int pos=n+1;
			rep(i, 1, n){
				while(pos>i && mod(i)+mod(pos-1)>=1<<k) --pos;
				pos=max(pos, i);
				if(n-pos+1&1) res^=1;
			}
		}
		if(res) ans^=1<<k;
	}
	cout<<ans;
}