← 返回题目列表

Codeforces · 1863/F

F. 除法、异或和征服

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。

在一次操作中,您将数组分为两部分:非空前缀和非空后缀。每个部分的值是其中所有元素的按位异或。接下来,丢弃值较小的部分。如果两个部分的值相等,您可以选择丢弃哪一个。将数组替换为剩余部分。

正在执行操作,直到数组的长度变为$$$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$$$ 的单个字符串,其中如果可以实现 $$$l = r = i$$$,则第 $$$i$$$ 个元素等于 1,否则等于 0。

示例

输入 #1

6
6
3 2 1 3 7 4
5
1 1 1 1 1
10
1 2 4 8 4 1 2 3 4 5
5
0 0 0 0 0
5
1 2 3 0 1
1
100500

输出 #1

111111
10101
0001000000
11111
11001
1

注意

在第一个测试用例中,对于从 $$$1$$$ 到 $$$n$$$ 的任何 $$$i$$$ 可以实现 $$$l = r = i$$$:

- 对于 $$$i=1$$$: $$$[1; 6] \右箭头 [1; 4] \右箭头 [1; 1]$$$;
- 对于 $$$i=2$$$: $$$[1; 6] \右箭头 [1; 3] \右箭头 [2; 3] \右箭头 [2; 2]$$$;
- 对于 $$$i=3$$$: $$$[1; 6] \右箭头 [1; 3] \右箭头 [3; 3]$$$;
- 对于 $$$i=4$$$: $$$[1; 6] \右箭头 [1; 4] \右箭头 [4; 4]$$$;
- 对于 $$$i=5$$$: $$$[1; 6] \右箭头 [5; 6] \右箭头 [5; 5]$$$;
- 对于 $$$i=6$$$: $$$[1; 6] \右箭头 [6; 6]$$$。

让我们仔细看看 $$$i = 2$$$。最初$$$l = 1$$$,$$$r = 6$$$。

1. 我们可以选择 $$$k = 3$$$ 并设置 $$$r = k = 3$$$,因为 $$$(3 \oplus 2 \oplus 1) = 0 \ge 0 = (3 \oplus 7 \oplus 4)$$$;
2. 接下来,我们可以选择 $$$k = 1$$$ 并设置 $$$l = k + 1 = 2$$$,因为 $$$3 \le 3 = (2 \oplus 1)$$$;
3. 最后,我们可以选择 $$$k = 2$$$ 并设置 $$$r = k = 2$$$,因为 $$$2 \ge 1$$$。