Even Subarrays

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

4
11
0
20

说明

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 $ .

题目描述：
给定一个整数数组 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ )。

找出数组 $ a $ 的子数组，其异或值的约数有偶数个。换句话说，找出所有索引对 $ (i, j) $ ( $ i \le j $ )，使得 $ a_i \oplus a_{i + 1} \oplus \dots \oplus a_j $ 的约数有偶数个。

例如，数字 $ 2 $, $ 3 $, $ 5 $ 或 $ 6 $ 的约数有偶数个，而 $ 1 $ 和 $ 4 $ 的约数有奇数个。在这个任务中，认为 $ 0 $ 的约数有奇数个。

这里的异或（XOR）表示按位异或操作。

输出子数组的数量，但乘以2022... 好吧，我们不要这样做。只需输出实际答案。

输入输出格式：
输入格式：
每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $ ( $ 1 \leq t \leq 10^4 $ )。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — 数组 $ a $ 的长度。

第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ )。

保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。

输出格式：
对于每个测试用例，输出其异或值有偶数个约数的子数组的数量。

输入输出样例：
输入样例 #1：
```
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3
```
输出样例 #1：
```
4
11
0
20
```

说明：
在第一个测试用例中，有 $ 4 $ 个子数组的异或值有偶数个约数：$ [3] $, $ [3,1] $, $ [1,2] $, $ [2] $。

在第二个测试用例中，有 $ 11 $ 个子数组的异或值有偶数个约数：$ [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] $。

在第三个测试用例中，没有子数组的异或值有偶数个约数，因为任何子数组的异或值要么是 $ 4 $ 要么是 $ 0 $。题目描述： 给定一个整数数组 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ )。 找出数组 $ a $ 的子数组，其异或值的约数有偶数个。换句话说，找出所有索引对 $ (i, j) $ ( $ i \le j $ )，使得 $ a_i \oplus a_{i + 1} \oplus \dots \oplus a_j $ 的约数有偶数个。 例如，数字 $ 2 $, $ 3 $, $ 5 $ 或 $ 6 $ 的约数有偶数个，而 $ 1 $ 和 $ 4 $ 的约数有奇数个。在这个任务中，认为 $ 0 $ 的约数有奇数个。 这里的异或（XOR）表示按位异或操作。 输出子数组的数量，但乘以2022... 好吧，我们不要这样做。只需输出实际答案。 输入输出格式： 输入格式： 每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $ ( $ 1 \leq t \leq 10^4 $ )。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — 数组 $ a $ 的长度。 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ )。 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。 输出格式： 对于每个测试用例，输出其异或值有偶数个约数的子数组的数量。 输入输出样例： 输入样例 #1： ``` 4 3 3 1 2 5 4 2 1 5 3 4 4 4 4 4 7 5 7 3 7 1 7 3 ``` 输出样例 #1： ``` 4 11 0 20 ``` 说明： 在第一个测试用例中，有 $ 4 $ 个子数组的异或值有偶数个约数：$ [3] $, $ [3,1] $, $ [1,2] $, $ [2] $。 在第二个测试用例中，有 $ 11 $ 个子数组的异或值有偶数个约数：$ [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] $。 在第三个测试用例中，没有子数组的异或值有偶数个约数，因为任何子数组的异或值要么是 $ 4 $ 要么是 $ 0 $。