千与千寻 - Problème

你在遗忘之丘（Forgotten Hill）认识一个怪人。今天，这个怪人想让你解决以下问题：

给定有限域 $\mathbb{F}_2$ 上的 $32$ 维向量空间 $\mathbb{F}_2^{32}$ 以及其中的 $n$ 个元素 $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$。求 $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$。

怪人曾经告诉过小蓝鱼（Little Cyan Fish）如何解决他的问题。然而，相关的记忆已被怪人模糊化了。因此，小蓝鱼希望你能解决这个怪人的问题。如果你对上述符号不熟悉，小蓝鱼用自然语言将上述问题描述如下：

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2 \dots a_n$（$0 \le a_i < 2^{32}$）。
定义 $B(l, r)$ 的值为：从 $a_l, a_{l+1} \dots a_r$ 中选择任意数量的数（可以是 $0$ 个），并将它们全部异或（XOR）起来，所能得到的所有可能异或值的集合。换句话说： $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
其中 $\oplus$ 表示按位异或运算。例如，$4 \oplus 6 = 2$，$1 \oplus 2 = 3$。
求对于所有 $1 \le l \le r \le n$，有多少个本质不同的集合 $B(l, r)$。

本题有多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

下一行包含 $n$ 个整数 $a_i$（$0 \le a_i < 2^{32}$）。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

对于每组测试数据，输出一行，包含一个整数，表示本质不同的 $B(l, r)$ 集合的数量，即 $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$。

5
3
1 2 3
4
10 12 17 33
6
1 0 9 8 7 3
8
9012 91829 9819 78 237 862 7672 2
10
0 1 2 4 8 16 32 64 128 256

对于第一组样例测试数据，合法的集合包括：$\{0, 1\}$，$\{0, 2\}$，$\{0, 3\}$，$\{0, 1, 2, 3\}$。

QOJ.ac