【题目】 

【题意】给定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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define ll long long#define lowbit(x) x&-xusing namespace std;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}int min(int a,int b){ return a
               
                0?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=200010;int n,A[maxn],B[maxn],cx[40][maxn],dx[maxn],ans=0;int main(){ n=read(); for(int i=1;i<=n;i++)A[i]=read(); for(int i=1;i<=n;i++)B[i]=read(); for(int k=0;k<28;k++){ if(!k)for(int i=1;i<=n;i++)cx[k][i]=((1<
               
              
             
            
           
          
         
        
       
      

 

【心路】这道题比赛最后10mins想到正解，没调出来，很气。

首先试了下不拆位，没思路，果然二进制题必须拆位。

然后想边算边进位，发现连续进位问题十分恐怖。

然后想先预处理连续进位，发现还是N^2。

然后突然想到要不预处理所有进位……比如2倍超过1<<k？

欸然后就会了……