CF2056F1 Xor of Median (Easy Version)

# Xor of Median (Easy Version) 这是问题的简单版本。版本之间的区别在于，在此版本中，对 $t$、$k$ 和 $m$ 的约束较低。只有在你解决了这个问题的所有版本之后，才能进行hack。 如果满足以下条件，则称长度为 $n$ 的整数序列 $a$ 为好序列： - 令 $\text{cnt}_x$ 为序列 $a$ 中 $x$ 的出现次数。对于所有满足 $0 \le i < j < m$ 的对 $(i, j)$，以下情况中至少有一种必须为真：$\text{cnt}_i = 0$，$\text{cnt}_j = 0$，或 $\text{cnt}_i \le \text{cnt}_j$。换句话说，如果 $i$ 和 $j$ 都出现在序列 $a$ 中，则 $a$ 中 $i$ 的出现次数小于或等于 $a$ 中 $j$ 的出现次数。 给定整数 $n$ 和 $m$。计算所有长度为 $n$、满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数的按位异或值。 请注意，$n$ 的值可能非常大，因此给出的是其二进制表示形式。 $ ^{\text{*}} $ 序列 $a$ 的中位数定义为序列中第 $\left\lfloor\frac{n + 1}{2}\right\rfloor$ 小的值。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 50$）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $k$ 和 $m$（$1 \le k \le 200$，$1 \le m \le 500$）——$n$ 的位数和序列 $a$ 中元素的上限。 每个测试用例的第二行包含一个长度为 $k$ 的二进制字符串——$n$ 的二进制表示形式，没有前导零。 保证所有测试用例中 $k$ 的总和不超过 $200$。

对于每个测试用例，输出一个整数，表示所有长度为 $n$、满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数的按位异或值。 ## 样例 #1 ### 样例输入 #1 ```cpp 6 2 3 10 2 3 11 5 1 11101 7 9 1101011 17 34 11001010001010010 1 500 1 ``` ### 样例输出 #1 ```cpp 3 2 0 8 32 0 ```

在第一个示例中，$n = 10_2 = 2$ 且 $m = 3$。所有元素小于 $m$ 的可能序列为：$[0, 0]$，$[0, 1]$，$[0, 2]$，$[1, 0]$，$[1, 1]$，$[1, 2]$，$[2, 0]$，$[2, 1]$，$[2, 2]$。它们都是好序列，所以答案是：$0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$。 在第二个示例中，$n = 11_2 = 3$ 且 $m = 3$。一些好序列为 $[2, 2, 2]$，$[1, 0, 1]$ 和 $[2, 0, 1]$。然而，序列 $[2, 0, 0]$ 不是好序列，因为 $\text{cnt}_0 = 2$，$\text{cnt}_2 = 1$。因此，如果我们设置 $i = 0$ 和 $j = 2$，则 $i < j$ 成立，但 $\text{cnt}_i \le \text{cnt}_j$ 不成立。