题解：P11651 [COCI 2024/2025 #4] Xor
Nangu
·
·
题解
我们按位计算答案。
设当前枚举到了第 k 位，下文计 b_i 表示 a_i 在第 k 位的值，c_i 表示 a_i 前 k-1 位的值（当 k=1 时 c_i=0）。
我们讲这三个贡献分开算，前两个是容易的，做第三个时，考虑讲 $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)$ 了。
代码：
```cpp
#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;
}
```