The problem What are the odds? is a very easy problem actually as long as you have basic knowledge about Nim Game. Sadly, it still took me about half an hour to get accepted due to a little mistake caused by careless reading and comprehension. I just thought about it as what I thought about regardless of the problem discription, and this is what I am good at. :(

The time complexity can be $O(n)$, but all is ok.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 500010;

int n;
ll ans;
int data[MAX_N], pre[MAX_N], suf[MAX_N];

int main() {
cin >> n;
ans = 1; pre[0] = 0;

for (int i = 1; i <= n; ++i) {
cin >> data[i];
pre[i] = pre[i - 1] ^ data[i];
if (i < n) ans += (pre[i] == 0);
}

map<int, int> ma;
suf[n + 1] = 0;
for (int i = n; i >= 1; --i) {
suf[i] = suf[i + 1] ^ data[i];
ma[suf[i]]++;
}

for (int i = 0; i < n; ++i) {
ma[suf[i + 1]]--;
ans += ma[pre[i]];
}
cout << ans << endl;
return 0;
}