Codeforces Round #539 (Div. 2)

Codeforces Round #539 (Div. 2)"/>

Codeforces Round #539 (Div. 2)

题目链接：C. Sasha and a Bit of Relax

题目：

Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.

Therefore, Sasha decided to upsolve the following problem:

You have an array a with n integers. You need to count the number of funny pairs (l,r) (l≤r). To check if a pair (l,r) is a funny pair, take mid=(l+r−1)/2 then if r−l+1 is an even number and al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar, then the pair is funny. In other words, ⊕ of elements of the left half of the subarray from ll to rr should be equal to ⊕of elements of the right half. Note that ⊕ denotes the bitwise XOR operation.

It is time to continue solving the contest, so Sasha asked you to solve this task.

Input

The first line contains one integer nn (2≤n≤3⋅10^5) — the size of the array.

The second line contains nn integers a1,a2,…,an (0≤ai<2^20) — array itself.

Output

Print one integer — the number of funny pairs. You should consider only pairs where r−l+1 is even number.

题目大意：

一个数组a，定义funny数对为（l,r）al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar（这个符号是异或） 求一共多少个funny数对。只用考虑r−l+1是偶数时。

思路：异或就是同0异1，异或有几个性质：一个数异或本身等于0、连续异或时改变顺序不影响结果。

若al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar，则al⊕al+1⊕…⊕ar=0，于是问题转化为：找共有多少(l,r)连续异或的结果为0。

用pre数组来存从a[1]连续异或到a[i]的值，pre[i]=pre[i-1]^a[i];  并且可以理解al⊕al + 1⊕…⊕ar=pre[r]⊕pre[l-1]，即pre[r]⊕pre[l-1]=0，则pre[r]=pre[l-1]，即计算有多少pre[r]=pre[l-1]。

普通计数会超时，由题意，易得l，r一个是奇数，另一个则是偶数，则l-1和r是同奇偶的，我们用一个二维数组cnt[2][maxc]来储存相同pre值得数量，cnt[1][]存技术，cnt[2][]存偶数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300010;
int a[maxn];
int pre[maxn];
int cnt[2][(1<<20)+3];int main()
{int n;cin>>n;ll ans=0;cnt[0][0]=1;for(int i=1;i<=n;i++){cin>>a[i];pre[i]=pre[i-1]^a[i];ans+=cnt[i%2][pre[i]];//pre[r]==pre[l-1],r和l-1同奇偶 cnt[i%2][pre[i]]++;}cout<<ans<<endl;
}