Codeforces #1113C | 哈喽哈咯

Written by razrlele 14:04 February 22, 2019

1113C

题意

给一个数组，然后求满足

\(a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r\)

的[l, r]子序列有多少个，其中\(\oplus\)表示异或计算。

思路

关键点在于如果满足条件的[l,r]存在，那么

\(a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} \oplus a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r == 0\)

也意味着

\( a_1 \oplus a_2 \oplus … \oplus a_l == a_1 \oplus a_2 \oplus … \oplus a_r\)

又因为[l,r]必须是包含偶数个数，所以l和r要么同时为奇数要么同时为偶数，令\( S_i = a_1 \oplus a_2 … \oplus a_i\) 所以题目就转换成了求满足l, r 同时为奇数或者同时为偶数且\(S_l == S_r\)存在多少。用两个数组分别维护奇数位和偶数位的S计数，然后对于\( a_i\), ans += count[i%2][ \(S_i\) ].

* File Name: C.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

#include <vector>

#include <set>

#include <deque>

#include <queue>

#include <algorithm>

#include <functional>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <string>

#include <cstring>

#include <string.h>

#include <map>

#include <cctype>

#include <list>

#include <stack>

#ifdef _WIN32

#define LLD "%I64d"

#else

#define LLD "%lld"

#endif

#define ll long long

using namespace std;

#define INF 0x3f3f3f3f

int a[2][1100000];

int main(int argc, char ** argv)

{

#ifdef LOCAL

string home_path(getenv("HOME"));

freopen((home_path+"/build/in.data").c_str(), "r", stdin);

//freopen((home_path+"/build/out.data").c_str(), "w", stdout);

#endif

int n;

while(~scanf("%d", &n)){

ll ans = 0;

ll xorv = 0;

a[1][0] = 1;

int t;

for(int i = 0; i < n ; i++){

scanf("%d", &t);

xorv ^= t;

ans += a[i%2][xorv];

a[i%2][xorv]++;

}

cout << ans << endl;

}

return 0;

}