A16619. Xor of Median (Hard Version)
编程题
省选/NOI-
知识点
题目描述
这是该问题的困难版本。本版本与其他版本的区别在于 $t$、$k$ 和 $m$ 的约束更高。只有在你解决了所有版本的问题后，才能进行 hack。
一个长度为 $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$ 的出现次数不超过 $j$ 的出现次数。
给定整数 $n$ 和 $m$。请计算所有长度为 $n$、满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数的按位异或和。
注意，$n$ 的值可能非常大，因此以其二进制表示给出。
$^*$ 序列 $a$ 的中位数定义为其第 $\left\lfloor\frac{n + 1}{2}\right\rfloor$ 小的元素。
一个长度为 $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$ 的出现次数不超过 $j$ 的出现次数。
给定整数 $n$ 和 $m$。请计算所有长度为 $n$、满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数的按位异或和。
注意，$n$ 的值可能非常大，因此以其二进制表示给出。
$^*$ 序列 $a$ 的中位数定义为其第 $\left\lfloor\frac{n + 1}{2}\right\rfloor$ 小的元素。
输入格式
每组测试包含多组数据。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下。
每组测试数据的第一行包含两个整数 $k$ 和 $m$（$1 \le k \le 2 \times 10^5$，$1 \le m \le 10^9$），分别表示 $n$ 的二进制长度和序列元素的上界。
第二行包含一个长度为 $k$ 的二进制字符串，表示 $n$ 的二进制表示，且没有前导零。
保证所有测试用例的 $k$ 之和不超过 $2 \times 10^5$。
每组测试数据的第一行包含两个整数 $k$ 和 $m$（$1 \le k \le 2 \times 10^5$，$1 \le m \le 10^9$），分别表示 $n$ 的二进制长度和序列元素的上界。
第二行包含一个长度为 $k$ 的二进制字符串，表示 $n$ 的二进制表示，且没有前导零。
保证所有测试用例的 $k$ 之和不超过 $2 \times 10^5$。
输出格式
对于每组测试数据，输出一个整数，表示所有长度为 $n$、满足 $0 \le a_i < m$ 的好序列 $a$ 的中位数的按位异或和。
输入输出样例
输入 #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$ 不成立。
在第二个样例中，$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$ 不成立。