分数: 400 点
问题陈述
有两个人,编号 0 和 1和一个变量 x 其初始值为 0。 现在两个人正在玩游戏。 游戏进行于 N 回合。应在 i- 第轮 (1 \leq i \leq N):
- 人 S_i 执行以下操作之一:
- 替换 x 与 x \oplus A_i,其中 \oplus 表示按位异或。
- 什么都不做。
人 0 旨在 x=0 在游戏结束时,Person 1 旨在 x \neq 0 游戏结束。
判断是否 x 变为 0 比赛结束时,两人发挥最佳。
解决 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 100
- 1 \leq N \leq 200
- 1 \leq A_i \leq 10^{18}
- S 是一个长度为 N 组成
0和1. - 输入的所有数字均为整数。
输入
输入由标准输入按以下格式给出。 第一行如下:
T
然后, T 测试用例如下。 每个测试用例均按以下格式给出:
N A_1 A_2 \cdots A_N S
输出
对于每个测试用例,打印一行包含 0 if x 变为 0 在游戏结束时,以及 1 否则。
示例输入 1
3 2 1 2 10 2 1 1 10 6 2 3 4 5 6 7 111000
示例输出 1
1 0 0
在第一个测试用例中,如果 Person 1 替换 x 与 0 \oplus 1=1,我们肯定有 x \neq 0 游戏结束时,无论选择Person 0.
在第二个测试用例中,无论选择Person 1, 人 0 可以使 x=0 有一个合适的选择。