← 返回题目列表

Codeforces · 2234/D

D. XOR、表达式和两个二进制数

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

给你一个整数$$$k$$$。有一个 $$$n$$$ 位二进制数 $$$a_1, a_2, \ldots, a_{2^k + 1}$$$ 的序列。数字 $$$a_1$$$ 和 $$$a_{2^k + 1}$$$ 是给你的,其他的未知。然后通过 $$$k$$$ 步骤如下填写未知数字:

  • 假设在第 $$$i$$$ 步骤之前,索引为 $$$p_1 \lt p_2 \lt \ldots \lt p_m$$$ 的数字已经被填充。 (在第一步之前,这些数字的索引为 $$$1, 2^{k} + 1$$$)。
  • 然后,对于从 $$$1$$$ 到 $$$m - 1$$$ 的每个 $$$j$$$,执行赋值 $$$a_{\frac{p_j + p_{j + 1}}{2}} := a_{p_j} \oplus a_{p_{j + 1}}$$$$$$^{\text{*}}$$$。
  • 这些分配同时发生,之后所有这些数字也被填充。

可以看出,这个过程总是完全填满所有数字。

这就是 $$$k = 2$$$ 和 $$$n = 3$$$ 的过程,其中最初 $$$a_1 = \texttt{010}, a_5 = \texttt{110}$$$:

  • 在第一步之前,填充索引为 $$$1, 5$$$ 的数字。因此,此操作将执行 $$$a_3 := a_1 \oplus a_5 = \texttt{010} \oplus \texttt{110} = \texttt{100}$$$。
  • 在第二步之前,填充索引为 $$$1, 3, 5$$$ 的数字。因此,此操作将执行 $$$a_2 := a_1 \oplus a_3 = \texttt{110}$$$ 和 $$$a_4 = a_{3} \oplus a_{5} = \texttt{010}$$$

您需要计算以下表达式: $$$x_1 \cdot y_1 + x_2 \cdot y_2 + \ldots + x_{2^k + 1} \cdot y_{2^k + 1}$$$,其中 $$$x_i$$$ 是第 $$$i$$$ 中设置的位数,$$$y_i$$$ 是第 $$$i$$$ 个数字中零位的数量。

$$$^{\text{*}}$$$$$x \oplus y$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的按位异或

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 30$$$) — 二进制数的长度和确定序列中二进制数数量的数字。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i \in \{\texttt{0}, \texttt{1}\}$$$) — $$$a_1$$$ 的值。

每个测试用例的第三行包含一个长度为 $$$n$$$ 的二进制字符串 $$$z$$$ ($$$z_i \in \{\texttt{0}, \texttt{1}\}$$$) — $$$a_{2^k + 1}$$$ 的值。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个整数——语句中表达式的值。

示例

输入
复制

4
3 2
010
110
1 1
0
0
2 2
01
00
7 30
1010111
0011010

输出
复制

10
0
3
12169074016

注意

在第一个测试用例中,声明中描述了该过程。生成的二进制数序列为 $$$[\texttt{010}, \texttt{110}, \texttt{100}, \texttt{010}, \texttt{110}]$$$。那么语句中的表达式等于 $$$1 \cdot 2 + 2 \cdot 1 + 1 \cdot 2 + 1 \cdot 2 + 2 \cdot 1 = 10$$$。

在第二个测试用例中,第一步我们有 $$$a_2 = a_1 \oplus a_3 = \texttt{0} \oplus \texttt{0} = \texttt{0}$$$。因此,生成的数字序列为 $$$[\texttt{0}, \texttt{0}, \texttt{0}]$$$。对于它,表达式的值为零。