这是问题的困难版本。版本之间的区别在于,在该版本中,对$$$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 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$k$$$ 和 $$$m$$$ ($$$1 \le k \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) - $$$n$$$ 中的位数以及序列 $$$a$$$ 中元素的上限。
每个测试用例的第二行包含一个长度为 $$$k$$$ 的二进制字符串 - $$$n$$$ 的二进制表示形式,不带前导零。
保证所有测试用例的 $$$k$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示长度为 $$$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 1000000000 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$$$ 不成立。