AT3943 [ARC092B] Two Sequences 二进制+拆位

这种出现异或的题一般来说都是进行二进制拆位，然后按位考虑的.   

我们考虑第 $i$ 位是否为 1.  

不妨模 $2^{i+1}$，排除前面的影响.   

那么一对 $a[k]+b[k]$ 中第 $i$ 位为 1 的条件是： 

1. 由后面进位，得 $i$ 位为 1.   

2. 两个位置都是 1，但是进位后还是 1.    

然后我们发现满足不等式 $2^i <=a[k]+b[k] < 2^{i+1}$ 或 $3 imes 2^i <= a[k]+b[k] < 4 imes 2^i$.   

然后这个可以枚举 $a$，二分求 $b$ 的范围.  

code: 

#include <bits/stdc++.h>         
#define N 400008   
#define ll long long         
#define setIO(s) freopen(s".in","r",stdin)       
using namespace std;           
int a[N],b[N],c[N],d[N];  
int main() 
{ 
	// setIO("input");   
	int i,j,n;  
	scanf("%d",&n);
	for(i=1;i<=n;++i)   
		scanf("%d",&a[i]); 
	for(i=1;i<=n;++i)   
		scanf("%d",&b[i]);                
	int ans=0,pow=1;   
	for(i=0;i<=28;++i) 
	{        
		for(j=1;j<=n;++j)  
			c[j]=a[j],d[j]=b[j];       
		for(j=1;j<=n;++j)    
		{
			c[j]%=(pow<<1);     
			d[j]%=(pow<<1);   
		}   
		sort(d+1,d+1+n);      
		int l,r,sum=0;     
		for(j=1;j<=n;++j)  
		{
			l=lower_bound(d+1,d+1+n,pow-c[j])-d;     
			r=lower_bound(d+1,d+1+n,2*pow-c[j])-d;   
			if(d[r]>=2*pow-c[j])     
				--r;      
			if(r>n)   
				--r; 
			if(l<=r)   
			    sum+=(r-l+1);             
			l=lower_bound(d+1,d+1+n,3*pow-c[j])-d;   
			r=lower_bound(d+1,d+1+n,4*pow-c[j])-d; 
			if(d[r]>=4*pow-c[j])     
				--r;      
			if(r>n)   
				--r;   
			if(l<=r)
			    sum+=(r-l+1);  
		}
		if(sum&1)     
			ans+=pow;     
		pow*=2;  
	}    
	printf("%d
",ans);  
	return 0; 
}