Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <cstdlib>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;
ll pre[maxn], a[maxn];
int num[(1 << 20) + 100][2];
int main()
{
	int n,cnt=1;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d", &a[i]);
		pre[i] = pre[i - 1] ^ a[i];
	}
	num[0][0] = 1;
	ll ans = 0;
	for(int i=1;i<=n;i++)
	{
		ans += num[pre[i]][i & 1];
		num[pre[i]][i & 1]++;
	}
	printf("%I64d
", ans);
	return 0;
}

C. Sasha and a Bit of Relax

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

Input

The first line contains one integer

The second line contains

Output

Print one integer — the number of funny pairs. You should consider only pairs where

Examples

Input

Copy

5
1 2 3 4 5

Output

Copy

Input

Copy

6
3 2 2 3 7 6

Output

Copy

Input

Copy

3
42 4 2

Output

Copy

Note

Be as cool as Sasha, upsolve problems!

In the first example, the only funny pair is

In the second example, funny pairs are

In the third example, there are no funny pairs.

这是一个异或问题，而且又有连续的一段进行异或，而异或有很多运算法则，我觉得很重要的就是交换律，所以这个可以用前缀和进行存储。

异或运算法则：

. a ⊕ a = 0

2. a ⊕ b = b ⊕ a

3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;

4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.

5. a ⊕ b ⊕ a = b.

这些就可以说明要求题目中的：al^al+1^...amid=amid+1^...ar；就可以转化成：pre[l-1]^pre[mid]=pre[mid]^pre[r],这个可以由上面的异或运算法则求出。

中间的pre[mid]可以约去，所以就是求pre[l-1]=pre[r]

接下来求这个pre[l-1]=pre[r]的方法是我上网查的，我觉得挺好的，就是：

用一个二维数组来存储，要求l到r之间所有数的个数为偶数，则必须是同为奇数或者同为偶数，意识到这个之后，二维数组的第二位可以设置成2，然后再看一维数组。

进行异或，则异或之后的值不会比2的20次方还大，因为这个数最多只有20位，所以就算这个二进制的二十位都是1，也差不多就是2的20次方左右。

所以一维数组的大小可以设置成2的20次方。

如果之后有数是和pre[i]一样，则之后会进行累加。

这个方法我觉得挺好的，可以用到别的题目上。

这个题目考了：异或，前缀和，还有就是怎么去求一段集合数目是偶数，且异或值一样的集合数量。

Codeforces Round #539 (Div. 2) C. Sasha and a Bit of Relax

相关推荐