CF1863F Divide, XOR, and Conquer

给定一个包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 的数组。 每次操作，你可以将数组分成两部分：一个非空前缀和一个非空后缀。每一部分的值为其所有元素的按位异或（bitwise XOR）。接下来，丢弃值较小的那一部分。如果两部分的值相等，你可以选择丢弃哪一部分。用剩下的部分替换原数组。 重复进行上述操作，直到数组长度变为 $1$。对于每个 $i$（$1 \le i \le n$），判断是否有可能最终只剩下原数组的第 $i$ 个元素。 形式化地说，有两个数 $l$ 和 $r$，初始时 $l=1$，$r=n$。当前数组状态为 $[a_l, a_{l+1}, \ldots, a_r]$。 只要 $l < r$，你就可以进行如下操作： - 从集合 $\{l, l+1, \ldots, r-1\}$ 中任选一个 $k$。记 $x = a_l \oplus a_{l+1} \oplus \ldots \oplus a_k$，$y = a_{k+1} \oplus a_{k+2} \oplus \ldots \oplus a_r$，其中 $\oplus$ 表示按位异或操作。 - 如果 $x < y$，则令 $l = k+1$。 - 如果 $x > y$，则令 $r = k$。 - 如果 $x = y$，可以任选 $l = k+1$ 或 $r = k$。 对于每个 $i$（$1 \le i \le n$），判断是否有可能最终达到 $l = r = i$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10\,000$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^{60}$）。 保证所有测试用例中 $n$ 的总和不超过 $10\,000$。

对于每个测试用例，输出一个长度为 $n$ 的字符串，第 $i$ 个字符为 $1$ 表示有可能最终只剩下第 $i$ 个元素，否则为 $0$。

在第一个测试用例中，对于任意 $i$（$1$ 到 $n$），都可以最终只剩下第 $i$ 个元素： - 对于 $i=1$：$[1; 6] \rightarrow [1; 4] \rightarrow [1; 1]$； - 对于 $i=2$：$[1; 6] \rightarrow [1; 3] \rightarrow [2; 3] \rightarrow [2; 2]$； - 对于 $i=3$：$[1; 6] \rightarrow [1; 3] \rightarrow [3; 3]$； - 对于 $i=4$：$[1; 6] \rightarrow [1; 4] \rightarrow [4; 4]$； - 对于 $i=5$：$[1; 6] \rightarrow [5; 6] \rightarrow [5; 5]$； - 对于 $i=6$：$[1; 6] \rightarrow [6; 6]$。 以 $i=2$ 为例，初始时 $l=1$，$r=6$。 1. 可以选择 $k=3$，由于 $(3 \oplus 2 \oplus 1) = 0 \ge 0 = (3 \oplus 7 \oplus 4)$，所以令 $r = k = 3$； 2. 接着选择 $k=1$，由于 $3 \le 3 = (2 \oplus 1)$，所以令 $l = k+1 = 2$； 3. 最后选择 $k=2$，由于 $2 \ge 1$，所以令 $r = k = 2$。 由 ChatGPT 4.1 翻译