CF2234D.XOR, Expression and Two Binary Numbers

You are given an integer $k$. There is a sequence of $n$-bit binary numbers $a_1, a_2, \ldots, a_{2^k + 1}$. The numbers $a_1$ and $a_{2^k + 1}$ are given to you, and the others are unknown. Then the unknown numbers are filled in as follows over $k$ steps:

• Suppose that before the $i$-th step, the numbers with indices $p_1 \lt p_2 \lt \ldots \lt p_m$ have already been filled. (Before the first step, these are the numbers with indices $1, 2^{k} + 1$).
• Then for each $j$ from $1$ to $m - 1$, the assignment $a_{\frac{p_j + p_{j + 1}}{2}} := a_{p_j} \oplus a_{p_{j + 1}}$$^{\text{∗}}$ is performed.
• These assignments happen simultaneously, and after that all these numbers also become filled.

It can be shown that this process always fills all numbers completely.

This is what the process looks like for $k = 2$ and $n = 3$, where initially $a_1 = \texttt{010}, a_5 = \texttt{110}$:

• Before the first step, the numbers with indices $1, 5$ are filled. Therefore, this operation will perform $a_3 := a_1 \oplus a_5 = \texttt{010} \oplus \texttt{110} = \texttt{100}$.
• Before the second step, the numbers with indices $1, 3, 5$ are filled. Therefore, this operation will perform $a_2 := a_1 \oplus a_3 = \texttt{110}$ and $a_4 = a_{3} \oplus a_{5} = \texttt{010}$

You need to compute the following expression: $x_1 \cdot y_1 + x_2 \cdot y_2 + \ldots + x_{2^k + 1} \cdot y_{2^k + 1}$, where $x_i$ is the number of set bits in the $i$-th number, and $y_i$ is the number of zero bits in the $i$-th number.

$^{\text{∗}}$$x \oplus y$ denotes the bitwise exclusive OR of numbers $x$ and $y$

给你一个整数 $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 步之前，仅有下标为 $1$ 和 $2^{k} + 1$ 的项已填入）。
• 然后，对每个 $j = 1, 2, \ldots, m - 1$，执行赋值操作：$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 步前，已填入下标为 $1, 5$ 的项。因此，执行 $a_3 := a_1 \oplus a_5 = \texttt{010} \oplus \texttt{110} = \texttt{100}$。
• 第 2 步前，已填入下标为 $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$ 个数中**置位比特（1 的个数）的数量，$y_i$ 表示第 $i$ 个数中零比特（0 的个数）**的数量。

$^{\text{∗}}$$x \oplus y$ 表示数字 $x$ 与 $y$ 的按位异或（bitwise exclusive OR）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n, k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 30$) — the length of the binary numbers and the number determining the number of binary numbers in the sequence.

The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in {\texttt{0}, \texttt{1}}$) — the value of $a_1$.

The third line of each test case contains a binary string $z$ of length $n$ ($z_i \in {\texttt{0}, \texttt{1}}$) — the value of $a_{2^k + 1}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output one integer — the value of the expression from the statement.

对于每个测试用例，输出一个整数——即题目陈述中表达式的值。

In the first test case, the process was described in the statement. The resulting sequence of binary numbers is $[\texttt{010}, \texttt{110}, \texttt{100}, \texttt{010}, \texttt{110}]$. Then the expression in the statement equals $1 \cdot 2 + 2 \cdot 1 + 1 \cdot 2 + 1 \cdot 2 + 2 \cdot 1 = 10$.

In the second test case, at the first step we have $a_2 = a_1 \oplus a_3 = \texttt{0} \oplus \texttt{0} = \texttt{0}$. Therefore, the resulting sequence of numbers is $[\texttt{0}, \texttt{0}, \texttt{0}]$. For it, the value of the expression is zero.

在第一个测试用例中，题目陈述中已描述了整个过程。最终得到的二进制数序列为 $[\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}]$。对该序列，表达式的值为零。