题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

· · 题解

本人没打，写篇题解。话说为啥有人觉得这是 DP 啊？

题目解法

由于异或的逆运算就是自身，所以异或是可以通过类似前缀和的方法来快速求区间和的。那么对于每一个区间，有：

\begin{aligned} s_r\oplus s_{l-1} &= k \\ s_r\oplus k&=s_{l-1}\end{aligned}

定义上一个区间的右端点位置为 lst，于是，我们就可以通过枚举右端点 r，如果存在一个 l(lst\le l<r) 使得 s_r\oplus k=s_l，那么就存在区间 (l,r] 符合条件了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,k;
ll a[N],s[N];
ll id[2005000],lst;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]^a[i];
    memset(id,-1,sizeof id);
    id[0]=0;
    ll ans=0;
    for(int r=1;r<=n;r++){
        ll x=s[r]^k;
        if(id[x]>=lst){
            ans++;
            lst=r;
        }
        id[s[r]]=r;
    }
    cout<<ans;
    return 0;
}