← 返回题目列表

AtCoder · agc045_a

A. 异或战斗

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

分数: 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 有一个合适的选择。