【题目】AtCoder Regular Contest 092 D - Two Sequences
【题意】给定n个数的数组A和数组B，求所有A[i]+B[j]的异或和(1<=i,j<=n)。n<=200000。
【算法】二分+模拟
【题解】将答案分成(A[i]+B[j]-A[i]^B[j])的异或和 以及 A[i]^B[j]的异或和，即单独考虑进位（后面部分很好算）。
二进制题目必须拆位，通过进位使第k位+1的数对必须满足 ( A[i] & ((1<<k)-1) ) + ( B[i] & ((1<<k)-1) ) >= (1<<k)。
首先预处理cx[k][i]=B[i] & ((1<<k)-1)，然后对所有cx[k]排序。（如果是累加预处理的话先全部处理出来再排序）
枚举数位k，然后枚举A[i] & ((1<<k)-1)，在cx[k-1]中二分出满足要求的数对个数%2后累加进答案。
最后异或和部分就很好算啦。
复杂度O(n*28*log n)。（好极限……）
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int ab(int x){return x>?x:-x;}
//int MO(int x){return x>=MOD?x-MOD:x;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=; int n,A[maxn],B[maxn],cx[][maxn],dx[maxn],ans=; int main(){
n=read();
for(int i=;i<=n;i++)A[i]=read();
for(int i=;i<=n;i++)B[i]=read();
for(int k=;k<;k++){
if(!k)for(int i=;i<=n;i++)cx[k][i]=((<<k)&B[i]);else
for(int i=;i<=n;i++)cx[k][i]=cx[k-][i]^((<<k)&B[i]);
}
for(int k=;k<;k++)sort(cx[k]+,cx[k]+n+);//
for(int k=;k<=;k++){
for(int i=;i<=n;i++){
dx[i]^=(<<(k-))&A[i];
int x=lower_bound(cx[k-]+,cx[k-]+n+,((<<k)-dx[i]))-cx[k-];
ans^=(((n-x+)%)<<k);
}
}
int a,b,c,d;
for(int k=;k<=;k++){
a=b=c=d=;
for(int i=;i<=n;i++)if((<<k)&A[i])b++;else a++;
for(int i=;i<=n;i++)if((<<k)&B[i])d++;else c++;
ans^=(((1ll*a*d%+1ll*b*c%)%)<<k);
}
printf("%d",ans);
return ;
}
【心路】这道题比赛最后10mins想到正解，没调出来，很气。
首先试了下不拆位，没思路，果然二进制题必须拆位。
然后想边算边进位，发现连续进位问题十分恐怖。
然后想先预处理连续进位，发现还是N^2。
然后突然想到要不预处理所有进位……比如2倍超过1<<k？
欸然后就会了……