题解 CF1322B 【Present】

Daidly · 2021-07-03 12:21:17 · 题解

由题可知，对答案每一位有贡献的是 (a[i]+a[j]) 的每一位，所以可以按位考虑。

• 两个数第 k 位的和，与前 k 位有联系。

不妨先求 a[j] 的前 i 位，用 b[j] 储存：

• 第一种：b[j]=a[j] \bmod 2^{k+1}，代码为：b[j]=a[j]%(1<<(i+1))。

• 第二种：b[j]=a[j] \And 2^{k+1}-1，比如取数 X=10101110 的前 4 位，只需要另找一个数 Y，令 Y 的前 4 位为 1，其余位为 0，即 Y=00001111，然后将 X 与 Y 进行按位与运算 (X \And Y=00001110) 即可得到 X 的前 4 位。代码为：b[j]=a[j]&((1<<(i+1))-1)。

效果一样，自行选择。

然后考虑 b[j_1]+b[j_2] 第 i 位为 1 的条件：

• 不进位：b[j_1]+b[j_2]\in[2^i,2^{i+1}-1]，代码为：(1<<i,(1<<(i+1))-1)。

• 进位：b[j_1]+b[j_2]\in[2^i\times2+2^i,(2^{i+1}-1)\times 2]，b[j_1]+b[j_2]\in[3\times 2^i,2^{i+2}-2]，代码为：(3<<i,(1<<(i+2))-2)。

由于 b 数组的顺序对答案没有影响，所以可以用 two-pointers 计算。

关于双指针函数：

bool tp(int x,int y){
    if(x>y)return 0;
    int num=0;
    for(int i=n,l=1,r=1;i;--i){
        while(l<=n&&b[i]+b[l]<x)l++;
        while(r<=n&&b[i]+b[r]<=y)r++;
        num+=r-l-(l<=i&&i<r);
    }
    return (num>>1)&1;//判断num除2是奇是偶 
}

设定为 bool 函数，计算 b[j_1]+b[j_2]\in[2^i,2^{i+1}-1]\cup [3\times 2^i,2^{i+2}-2] 的个数是奇是偶。

当然，在这里我们可以分开算，然后再与上两个 bool 函数返回值：

int cnt=tp(1<<i,(1<<(i+1))-1)^tp(3<<i,(1<<(i+2))-2);

若在区间 [2^i,2^{i+1}-1] 和区间 [3\times 2^i,2^{i+2}-2] 中有且只有一个区间有奇数个 (b[j_1],b[j_2]) 满足条件（根据 奇 + 偶 = 奇），则更新答案。

最后一点，判断 i 的最大值（最大计算到前几位）：

由题可知：答案为两数之和再取异或值，所以答案的位数小于等于最大的数对和位数，因为 1\leq a_i\leq 10^7，所以两数之和小于等于 2\times 10^7，又因为 2^{25}=33554432>2\times 10^7，所以 i\leq 25 即可（这里位数指二进制位数）。

整体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 400005
int n,a[MAXN],b[MAXN],ans;
bool tp(int x,int y){
    if(x>y)return 0;
    int num=0;
    for(int i=n,l=1,r=1;i;--i){
        while(l<=n&&b[i]+b[l]<x)l++;
        while(r<=n&&b[i]+b[r]<=y)r++;
        num+=r-l-(l<=i&&i<r);
    }
    return (num>>1)&1;//判断num除2是奇是偶 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    //2^25=33554432>2*1e7
    for(int i=0;i<=25;++i){
        for(int j=1;j<=n;++j){
            b[j]=a[j]%(1<<(i+1));
            //b[j]=a[j]&((1<<(i+1))-1)
        }
        sort(b+1,b+n+1);
        int cnt=tp(1<<i,(1<<(i+1))-1)^tp(3<<i,(1<<(i+2))-2);
        ans+=cnt*(1<<i);
    }
    cout<<ans;
    return 0;
}