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

huangleyi0129 · 2025-02-01 19:35:31 · 题解

结果为一堆数异或，故考虑逐位确定。

对于第 w 位，只需要考虑 a_i 第 w 位为 1 的数量（需要乘上 n 或 n-1，视其部分意义而定）和 a_i+a_j 在第 w 位产生进位的数量。

由于是异或运算，只需关注此数量的奇偶性，故直接加起来即可。

具体地，对于第二项，在有序数组中双指针即可计算。

枚举位的同时做一个按位的基数排序即可做到 O(nw)，其中 w 取 30。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=500005,W=30;
int a[N],b[N],n,ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    int u,j;
    long long cnt;
    for(int w=0;w<=W;++w)
    {
        u=(1<<w)-1,j=n+1,cnt=0;
        for(int i=1;i<n;++i)
        {
            while(j-1>i&&(a[j-1]&u)+(a[i]&u)>u)
                --j;
            if(j<=i)
                j=i+1;
            cnt+=n-j+1;
        }
        j=0;
        for(int i=1;i<=n;++i)
            if((a[i]>>w)&1)
                cnt+=n-1;
            else
                b[++j]=a[i];
        if(cnt&1)
            ans|=1<<w;
        for(int i=1;i<=n;++i)
            if((a[i]>>w)&1)
                b[++j]=a[i];
        memcpy(a,b,sizeof a);
    }
    for(int i=1;i<=n;++i)
        ans^=(a[i]+a[i]);
    cout<<ans;
    return 0;
}