异或类经典题型

· · 个人记录

前言

此乃小 Oler 记录学习的文章，从今日后，还会进行详细的修订。

思想 No.1 （结合二进制运算）

浅析 [性质 1]

由于位运算是位独立的，我们可以把它按二进制拆分为 0,1 的序列 a_i。

由于异或具有自反性，类比前缀和，记 S_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i，那么有 [l,r] 内的数的异或值则为 S_r \oplus S_{l-1}。

例题

①. P9236 [蓝桥杯 2023 省 A] 异或和之和

②. P3917 异或序列

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+10;
int n,a[N],s[N];
signed main() {
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int ans=0;
    for(int i=0;i<=20;i++) {
        for(int j=1;j<=n;j++) {
            if((a[j]>>i)&1) s[j]=s[j-1]^1;
            else s[j]=s[j-1];
        }
        int l=0,r=0;
        for(int j=0;j<=n;j++) {
            if(s[j]==0) l++;
            else r++;
        }
        ans+=(1ll<<i)*l*r;
    }
    printf("%lld\n",ans);
    return 0;
}

有待开发....