「题解」「arc092_b」Two Sequences

ARC092B ,一道比较好的 位运算 的题目。

题目链接:AtCoder Regular Contest 092 D – Two Sequences

题目

ARC092B 但实际上他是 ARC092D。

题目翻译

长度为 $n(1\leq n\leq 2\times 10^5)$ 的数列 $\{a _ n\},\{b _ n\}(0\leq a _ i,b _ i\leq 2^{28})$。现在对于 $n^2$ 个 $(a _ i,b _ j),i,j\in[1,n]$,求所有 $(a _ i,b _ j)$ 的 $a _ i+b _ j$ 的异或和。

题解

思路

按位考虑,发现对于第 $i$ 位(从 $0$ 开始计数),设 $\text{T}=2^i$,如果将两数列同时对 $2\text{T}$ 取模,那么可以有 $(a _ i+b _ j)\in[0,4\text{T}-2]$。设 $S=(a _ i+b _ j)$,对 $S$ 分类讨论。

  1. $S\in[0,\text{T})$,则这两个数加起来的结果第 $i$ 位为 $0$。
  2. $S\in[\text{T},2\text{T})$,则这两个数加起来的结果第 $i$ 位为 $1$。
  3. $S\in[2\text{T},3\text{T})$,则这两个数加起来的结果第 $i$ 位为 $0$。
  4. $S\in[3\text{T},4\text{T})$,则这两个数加起来的结果第 $i$ 位为 $1$。

那么我们就可以发现对于一个确定的 $a _ i$,与之和的第 $i$ 为 $1$ 的 $b _ j$ 满足:

$$b _ j\in[\text{T}-a _ i,2\text{T}-a _ i)\cup[3\text{T}-a _ i,4\text{T}-a _ i)$$

排序后二分求区间长度即可。

代码

$4\text{T}$ 要开 long long

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll; //记得开 long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

int n;
vector<ll> a,b,ta,tb;

int main(void){
    n=read();
    for(reg int i=1;i<=n;++i){ //读入 a
        static ll x;
        x=read();
        a.push_back(x);
    }
    for(reg int i=1;i<=n;++i){ //读入 b
        static ll x;
        x=read();
        b.push_back(x);
    }
    reg ll ans=0;
    for(reg int i=0;i<30;++i){ //枚举每一位
        ta=a,tb=b; //复制一份 a,b
        reg ll T=(1<<i),mod=(T<<1);
        for(reg int j=0;j<n;++j){
            ta[j]&=mod-1;
            tb[j]&=mod-1; //可以用 & 运算代替这里的取模(对 2 的幂次取模)
        }
        sort(tb.begin(),tb.end()); //排序
        reg int cnt=0;
        for(reg int j=0;j<n;++j){ //求区间长度
            cnt+=lower_bound(tb.begin(),tb.end(),T*2-ta[j])-lower_bound(tb.begin(),tb.end(),T-ta[j]);
            cnt+=lower_bound(tb.begin(),tb.end(),T*4-ta[j])-lower_bound(tb.begin(),tb.end(),T*3-ta[j]);
        }
        if(cnt&1) //最后求异或的贡献
            ans|=T;
    }
    printf("%lld\n",ans); //输出答案
    return 0;
}