311259: CF1957D. A BIT of an Inequality
Description
You are given an array $a_1, a_2, \ldots, a_n$. Find the number of tuples ($x, y, z$) such that:
- $1 \leq x \leq y \leq z \leq n$, and
- $f(x, y) \oplus f(y, z) > f(x, z)$.
We define $f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$, where $\oplus$ denotes the bitwise XOR operation.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output a single integer on a new line — the number of described tuples.
ExampleInput3 3 6 2 4 1 3 5 7 3 7 2 1Output
4 0 16Note
In the first case, there are 4 such tuples in the array $[6, 2, 4]$:
- ($1$, $2$, $2$): $(a_1 \oplus a_2) \oplus (a_2) = 4 \oplus 2 > (a_1 \oplus a_2) = 4$
- ($1$, $1$, $3$): $(a_1) \oplus (a_1 \oplus a_2 \oplus a_3) = 6 \oplus 0 > (a_1 \oplus a_2 \oplus a_3) = 0$
- ($1$, $2$, $3$): $(a_1 \oplus a_2) \oplus (a_2 \oplus a_3) = 4 \oplus 6 > (a_1 \oplus a_2 \oplus a_3) = 0$
- ($1$, $3$, $3$): $(a_1 \oplus a_2 \oplus a_3) \oplus (a_3) = 0 \oplus 4 > (a_1 \oplus a_2 \oplus a_3) = 0$
In the second test case, there are no such tuples.
Output
1. $1 \leq x \leq y \leq z \leq n$，且
2. $f(x, y) \oplus f(y, z) > f(x, z)$。
其中，$f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$，$\oplus$ 表示按位异或操作。
输入数据格式：
- 第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) —— 测试用例的数量。
- 每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)。
- 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)。
- 保证所有测试用例的 $n$ 之和不超过 $10^5$。
输出数据格式：
- 对于每个测试用例，输出一个整数，即满足条件的元组的数量。
示例：
输入：
```
3
3
6 2 4
1
3
5
7 3 7 2 1
```
输出：
```
4
0
16
```题目大意：给定一个数组 $a_1, a_2, \ldots, a_n$，找出满足以下条件的元组 ($x, y, z$) 的数量： 1. $1 \leq x \leq y \leq z \leq n$，且 2. $f(x, y) \oplus f(y, z) > f(x, z)$。 其中，$f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$，$\oplus$ 表示按位异或操作。 输入数据格式： - 第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) —— 测试用例的数量。 - 每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)。 - 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)。 - 保证所有测试用例的 $n$ 之和不超过 $10^5$。 输出数据格式： - 对于每个测试用例，输出一个整数，即满足条件的元组的数量。 示例： 输入： ``` 3 3 6 2 4 1 3 5 7 3 7 2 1 ``` 输出： ``` 4 0 16 ```