【异或运算与加减法的禁断结合】题解：P11651 [COCI 2024/2025 #4] Xor

· · 题解

复健笑传之 Count Count Bit。

还记得第一次看见位运算于加减法同时出现，心情是多么的目力。究竟是谁发明的这几把玩意！然后便思索如何处理进位的问题。然后不知不觉摸鱼去了。

然后我就退役了。然后我到现在都不知道这一类题该怎么做。

下文中，对于二进制位，我们从 0 开始数。

求一堆东西的异或和。我们可以枚举它的每一个二进制位，尝试判断上面是 0 还是 1。

答案是一堆数的异或和。所以，如果我们想知道第 i 位是 0 还是 1，我们需要数出第 i 位是 1 的数有多少个。答案也是一堆数的和的异或和。所以，我们要完成这样一件事情：

给定两个正整数 A 和 B，快速判断 A+B 的二进制的第 i 位是 0 还是 1。

我们当然可以直接加起来在上左移右移之类的东西。但这样我们就回到原点了。毕竟我们面对的不是一对数，而是很多对数。位运算是不进位的，加减法是进位的。如果它们混在一起，会对优化带来麻烦。我们必须转化或去掉其中之一。

但我不会。

但首先，我们注意到，如果只是关注第 i 位，那么第 i+1,i+2 等位上是否进位我们是不用考虑的。所以我们可以像 10 进制下对 10^k 取模，来获取末 k 位数字一样，我们将数字对 2^k 取模，来获取末 k 个二进制位。前面的可以丢掉方便处理。

然后我们想，假设 A+B 的第 i 位是 1，那么，其他位上是 0 是 1 我们都不关心。i 的上面顶多会进一位，i 的下面有 i-1 个位。所以我们可以通过枚举是否进位来得到，当 A+B 的第 i 位为 1 时，A+B 的大小范围。

就像下面这样上面这几句话或许有点拗口

\color{blue}{0}\color{red}{1}\color{black}{000000} \le A+B \le \color{blue}{0}\color{red}{1}\color{black}{111111} \ 或 \ \color{blue}{1}\color{red}{1}\color{black}{000000} \le A+B \le \color{blue}{1}\color{red}{1}\color{black}{111111}

上面红的部分就是我们说的第 i 位。蓝色的就是进的位。黑色的就是我们不管心的那一坨 i-1 个位。

将上面的二进制变成十进制就是这样：

2^i \le A+B \le 2^{i+1}-1 \ 或 \ 3 \times2^i \le A+B \le 2^{i+2}-1

然后你就把左移右移改成了大小比较，然后就能和加减法兼容了。然后你就会这道题了。然后我会了。然后我忘了。然后我退役了。

最右边的 2^{i+2}-1 是取不到的，丢掉。然后我们设 u=2^i。把 所有满足 a_i+a_j \ge u 的数对数出来，减去 a_i+a_j \ge 2u 的，再加上 a_i+a_j \ge 3u 的，就得到答案了。

求一个数组里有多少个 a_i+a_j\ge u，双指针就够了。给式子移个项就行。

然后这道题就做完了。

哦孩子们我们还要满足 i\le j 所以代码里有一点点细节。

哦孩子们这题卡常我懒得基数排序了直接用快读日过去了。

#include <bits/stdc++.h>
namespace IO{
    char buff[1<<21],*P1OfFastIO=buff,*P2OfFastIO=buff;
    #define getch() (P1OfFastIO==P2OfFastIO&&(P2OfFastIO=((P1OfFastIO=buff)+fread(buff,1,1<<21,stdin)),P1OfFastIO==P2OfFastIO)?EOF:*P1OfFastIO++)
    template<typename T>
    void read(T &x){char CHOfFastIO=getch();int fl=1;x=0;while(CHOfFastIO>'9'||CHOfFastIO<'0'){if(CHOfFastIO=='-')fl=-1;CHOfFastIO=getch();}while(CHOfFastIO<='9'&&CHOfFastIO>='0'){x=x*10+CHOfFastIO-48;CHOfFastIO=getch();}x*=fl;}
    template<typename T,typename ...Args>
    void read(T &x,Args& ...args){read(x);read(args...);}
    char obuf[1<<21],*P3OfFastIO=obuf;
    inline void putch(char CHOfFastIO){if(P3OfFastIO-obuf<(1<<21))*P3OfFastIO++=CHOfFastIO;else fwrite(obuf,P3OfFastIO-obuf,1,stdout),P3OfFastIO=obuf,*P3OfFastIO++=CHOfFastIO;}
    char CHOfFastIO[100];template<typename T>
    void write(T x){if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)CHOfFastIO[++top]=x%10+48,x/=10;while(top)putch(CHOfFastIO[top]),top--;}
    template<typename T,typename ...Args>
    void write(T x,Args ...args){write(x);write(args...);}
    inline void flush(){fwrite(obuf,P3OfFastIO-obuf,1,stdout);}
}using namespace IO;
using namespace std;
typedef long long LL;
const int maxn=5e5+7;
const LL inf=1e18+7;
LL N,a[maxn],b[maxn];
inline LL solve(LL p){
    LL ret=0;
    LL mod=(1LL<<(p+1)),u=(1LL<<p);
    for(int i=1;i<=N;i++)b[i]=a[i]%mod;
    sort(b+1,b+N+1);b[N+1]=inf;
    //for(int i=1;i<=N;i++)cout<<b[i]<<' ';cout<<endl;
    for(int i=1,p=N+1;i<=N;i++){
        while(p!=0&&b[p]+b[i]>=u)--p;
        ret+=N-max(p,i-1);
    }
    //cout<<"ret: "<<ret<<endl;
    for(int i=1,p=N+1;i<=N;i++){
        while(p!=0&&b[p]+b[i]>=u*2)--p;
        ret-=N-max(p,i-1);
    }
    //cout<<"ret: "<<ret<<endl;
    for(int i=1,p=N+1;i<=N;i++){
        while(p!=0&&b[p]+b[i]>=u*3)--p;
        ret+=N-max(p,i-1);
    }
    //cout<<"ret: "<<ret<<endl;
    return ret&1;
}
int main(){
    //scanf("%lld",&N);
    read(N);
    //for(int i=1;i<=N;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=N;i++)read(a[i]);
    LL ans=0;
    for(int p=0;p<=30;p++)
        if(solve(p))ans|=(1LL<<p);
    //printf("%lld",ans);
    write(ans);flush();
    return 0;
}