Codeforces Round #841 (Div. 2) and Divide by Zero 2022

C. Even Subarrays

https://codeforces.com/contest/1731/problem/C

2.5 seconds / 256 megabytes

standard input / standard output

### Problem

You are given an integer array $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Find the number of subarrays of $a$ whose $\operatorname{XOR}$ has an even number of divisors. In other words, find all pairs of indices $(i, j)$ ($i \le j$) such that $a_i \oplus a_{i + 1} \oplus \dots \oplus a_j$ has an even number of divisors.

For example, numbers $2$, $3$, $5$ or $6$ have an even number of divisors, while $1$ and $4$ — odd. Consider that $0$ has an odd number of divisors in this task.

Here $\operatorname{XOR}$ (or $\oplus$) denotes the bitwise XOR operation.

Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.

### Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

### Output

For each test case, print the number of subarrays, whose $\operatorname{XOR}$ has an even number of divisors.

Input

4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

Output

4
11
0
20

### Note

In the first test case, there are $4$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[3]$, $[3,1]$, $[1,2]$, $[2]$.

In the second test case, there are $11$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[4,2]$, $[4,2,1]$, $[4,2,1,5]$, $[2]$, $[2,1]$, $[2,1,5]$, $[2,1,5,3]$, $[1,5,3]$, $[5]$, $[5,3]$, $[3]$.

In the third test case, there is no subarray whose $\operatorname{XOR}$ has an even number of divisors since $\operatorname{XOR}$ of any subarray is either $4$ or $0$.

### 题解

#### 朴素思路

$$\underset{i=l}{\overset{r}{\operatorname{XOR}}}\,a_i=prexor_r\,\operatorname{XOR}\,prexor_{l-1}$$

#### 对于每个完全平方数，是否存在子序列的 XOR 值等于它？

$$b=prexor_i\,\operatorname{XOR}\,k^2$$

$k^2$ 代表枚举的完全平方数，其中 $k\leq\sqrt n$.

$b$ 代表着满足子序列 XOR 为 $k^2$ 的子序列左端点。

### 代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int MAXN = 2e5 + 10;
int n;
int a[MAXN], cnt_prexor[MAXN * 2];

void solve()
{
memset(cnt_prexor, 0, sizeof(cnt_prexor));
cnt_prexor[0] = 1;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int cnt_odd = 0, cur_xor = 0;
for (int i = 0; i < n; i++)
{
cur_xor ^= a[i];
for (int j = 0; j * j < 2 * n; j++)
{
int l_prexor = cur_xor ^ (j * j);
if (l_prexor < 2 * n)
cnt_odd += cnt_prexor[l_prexor];
}
cnt_prexor[cur_xor]++;
}
int ans = (n + 1) * n / 2 - cnt_odd;
cout << ans << endl;
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}