专栏文章

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

ff_hxr_
P11651题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipdgwyf
此快照首次捕获于
2025/12/03 10:12
3 个月前
此快照最后确认于
2025/12/03 10:12
3 个月前
查看原文
复健笑传之 Count Count Bit。
还记得第一次看见位运算于加减法同时出现，心情是多么的目力。究竟是谁发明的这几把玩意！然后便思索如何处理进位的问题。然后不知不觉摸鱼去了。
然后我就退役了。然后我到现在都不知道这一类题该怎么做。
下文中，对于二进制位，我们从 00 开始数。
求一堆东西的异或和。我们可以枚举它的每一个二进制位，尝试判断上面是 00 还是 11。
答案是一堆数的异或和。所以，如果我们想知道第 ii 位是 00 还是 11，我们需要数出第 ii 位是 11 的数有多少个。答案也是一堆数的和的异或和。所以，我们要完成这样一件事情：
给定两个正整数 AA 和 BB，快速判断 A+BA+B 的二进制的第 ii 位是 00 还是 11。
我们当然可以直接加起来在上左移右移之类的东西。但这样我们就回到原点了。毕竟我们面对的不是一对数，而是很多对数。位运算是不进位的，加减法是进位的。如果它们混在一起，会对优化带来麻烦。我们必须转化或去掉其中之一。
但我不会。
但首先，我们注意到，如果只是关注第 ii 位，那么第 i+1,i+2i+1,i+2 等位上是否进位我们是不用考虑的。所以我们可以像 1010 进制下对 10k10^k 取模，来获取末 kk 位数字一样，我们将数字对 2k2^k 取模，来获取末 kk 个二进制位。前面的可以丢掉方便处理。
然后我们想，假设 A+BA+B 的第 ii 位是 11，那么，其他位上是 00 是 11 我们都不关心。ii 的上面顶多会进一位，ii 的下面有 i−1i-1 个位。所以我们可以通过枚举是否进位来得到，当 A+BA+B 的第 ii 位为 11 时，A+BA+B 的大小范围。
就像下面这样上面这几句话或许有点拗口
01000000≤A+B≤01111111 或 11000000≤A+B≤11111111\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}
上面红的部分就是我们说的第 ii 位。蓝色的就是进的位。黑色的就是我们不管心的那一坨 i−1i-1 个位。
将上面的二进制变成十进制就是这样：
2i≤A+B≤2i+1−1 或 3×2i≤A+B≤2i+2−12^i \le A+B \le 2^{i+1}-1 \ 或 \ 3 \times2^i \le A+B \le 2^{i+2}-1
然后你就把左移右移改成了大小比较，然后就能和加减法兼容了。然后你就会这道题了。然后我会了。然后我忘了。然后我退役了。
最右边的 2i+2−12^{i+2}-1 是取不到的，丢掉。然后我们设 u=2iu=2^i。把 所有满足 ai+aj≥ua_i+a_j \ge u 的数对数出来，减去 ai+aj≥2ua_i+a_j \ge 2u 的，再加上 ai+aj≥3ua_i+a_j \ge 3u 的，就得到答案了。
求一个数组里有多少个 ai+aj≥ua_i+a_j\ge u，双指针就够了。给式子移个项就行。
然后这道题就做完了。
哦孩子们我们还要满足 i≤ji\le j 所以代码里有一点点细节。
哦孩子们这题卡常我懒得基数排序了直接用快读日过去了。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...