题解：P11651 [COCI 2024/2025 #4] Xor

Targanzqq · 2025-10-15 18:57:35 · 题解

看到异或，我们首先应该想按位讨论。

那么我们就可以把某一位和它后面的位抽出来，去找它们加起来之后这一位为1的数有多少。

因此我们令 b_{i,k} 表示 a_i \bmod (2^{k+1}-1) 的结果，就能得到它的后 k 位。

首先我们对这个序列排序，接下来我们就可以分类讨论需要加起来的两个数：第 k 位都是 0；一个是 0，另一个是 1；两个都是 1。

其实不难发现，对于第 k 位相同的情况，我们需要让后面进位；对于第 k 位 不同 的情况，我们需要让后面不进位。所以双指针找一下进位的分界点就可以。

这题没卡双 \log。所以我们可以愉快地使用 O(n\log n\log v) 的时间复杂度通过本题。其实每次排序之后我们可以从当前位为 0/1 的分界点分出两个序列，然后再根据这些数的更高一位的值归并，就能优化到 O(n\log v)。

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
using namespace std;

int n,a[500005],b[500005];

signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int k=30;k>=0;k--){
        int res=0;
        for(int i=1;i<=n;i++){
            b[i]=a[i]&((1ll<<(k+1))-1);
        }
        sort(b+1,b+n+1);
        int pos=n+1;
        for(int i=1;i<=n;i++){
            if(b[i]&(1ll<<k)){pos=i;break;}
        }
        // for(int i=1;i<=n;i++)cout<<b[i]<<" ";
        // cout<<"\n";
        //cout<<k<<" "<<pos<<" ";
        for(int l=1;l<pos;l++){
            if((2*b[l])&(1ll<<k)){
                for(int i=l,j=l;i<pos;i++){
                    while(((b[j]+b[i])&(1ll<<k))&&j>=1)j--;
                    res+=i-j;
                }
                break;
            }
        }
        //cout<<res<<"\n";
        for(int i=pos,j=pos-1;i<=n;i++){
            while(((b[j]+(b[i]^(1<<k)))&(1ll<<k))&&j>=1)j--;
            res+=j;
        }
        //cout<<res<<"\n";
        for(int l=pos;l<=n;l++){
            if((2*(b[l]^(1ll<<k)))&(1ll<<k)){
                for(int i=l,j=l;i<=n;i++){
                    while((((b[j]^(1<<k))+(b[i]^(1<<k)))&(1ll<<k))&&j>=pos)j--;
                    res+=i-j;
                }
                break;
            }
        }
        //cout<<res<<"\n";
        ans+=(res%2)*(1ll<<k);
    }
    cout<<ans;
}