← 返回题目列表

Codeforces · 2056/F1

F1. 中值异或(简单版)

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

这是问题的简单版本。版本之间的区别在于,在该版本中,对$$$t$$$、$$$k$$$ 和$$$m$$$ 的约束较低。只有解决了该问题的所有版本,您才能破解。

如果满足以下条件,则 $$$n$$$ 整数的序列 $$$a$$$ 被称为良好:

- 令 $$$\text{cnt}_x$$$ 为 $$$x$$$ 在序列 $$$a$$$ 中出现的次数。对于所有 $$$0 \le i < j < m$$$,至少必须满足以下条件之一:$$$\text{cnt}_i = 0$$$、$$$\text{cnt}_j = 0$$$ 或 $$$\text{cnt}_i \le \text{cnt}_j$$$。换句话说,如果 $$$i$$$ 和 $$$j$$$ 都出现在 $$$a$$$ 序列中,则 $$$i$$$ 在 $$$a$$$ 中出现的次数小于或等于 $$$j$$$ 在 $$$a$$$ 中出现的次数。

给定整数 $$$n$$$ 和 $$$m$$$。计算长度为 $$$n$$$ 且 $$$0\le a_i < m$$$ 的所有好序列 $$$a$$$ 的中位数 $$$^{\text{∗}}$$$ 的按位异或值。

请注意,$$$n$$$ 的值可能非常大,因此您会得到它的二进制表示形式。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 的所有好序列 $$$a$$$ 的中位数的按位异或,其中 $$$0\le a_i < m$$$。

示例

输入 #1

6
2 3
10
2 3
11
5 1
11101
7 9
1101011
17 34
11001010001010010
1 500
1

输出 #1

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$$$ 不成立。