题解:Xor Sum 2

算法

地址：https://vjudge.net/problem/AtCoder-arc098b

Published

February 8, 2022

Content note — Known errors · 明显错误

Xor Sum 2 的核心性质描述有误，代码思路和文字说法不一致。

多个数“全部按位与为 0”不足以推出异或和等于普通和，例如 1、1、2 的整体 AND 为 0 但条件不成立。
正确条件应是当前集合各二进制位至多出现一次；代码用 res & a[q] 检查冲突更接近正确做法。

题解 : Xor Sum 2

1.题意

地址：https://vjudge.net/problem/AtCoder-arc098_b

1.1 Problem Statement

There is an integer sequence A of length N.

Find the number of the pairs of integers l and r (\(1 \leq l \leq r \leq N\)) that satisfy the following condition:

\(A_l xor A_{l+1} xor ... xor A_r=A_l + A_{l+1} + ... + A_r\)

Here, xor denotes the bitwise exclusive OR.

1.2 Constraints

\(1 \leq N \leq 2 \times 10^5\)
\(0 \leq A_i < 2^{20}\)
All values in input are integers.

大致意思就是一个序列问它有多少个连续的子序列满足这个子序列的异或和等于这个子序列的和

2.思路

异或和这种东西，往往出了就要找一点小性质，但一般有不会很难。

性质

这个题首先异或和等于和，考虑二进制下的加法，如果异或和等于和的话，那么这些数的任意一个相同的位都不会同事出现1个以上个1。

比如说8 4 1这三个数

二进制下：

1	0	0	0
	1	0	0
			1

这三个数的任意相同位上都没有超过一个1。他们的和等于异或和。

判断方法很简单，只要把它们全都 & 一下如果结果不是0就一定有某些位出现了一个以上的1

所以对于一个连续子串，如果把他们全都&起来答案为0那么他们的异或和等于和

优化

很显然\(n^2\)过不了1e5所以要优化。

可以尺取

因为很显然以a[i]为开头的连续子串的结尾位置j一定小于等于以a[i+1]为开头的子串的结尾位置。因为少&一个数总不可能加剧&出非0数

3：代码

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5+7;
int a[MAXN];
template <typename _TP>
inline _TP qread(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
    X=w?-X:X;
    return X;
}
inline int Max(const int a,const int b){
    return a>b?a:b;
}
int main(){
    int n;
    qread(n);
    for(int i=1;i<=n;i++){
        qread(a[i]);
    }
    int res = 0,p = 1,q = 1;
    long long ans = 0;
    while(true){
        if(p>q)q=p;
        while(!(a[q]&res) && q<=n){
            res^=a[q++];
        }
        ans+=q-p;
        res^=a[p];
        if(++p>n)break;
    }
    cout<<ans;
    return 0;
}