CF2234D XOR, Expression and Two Binary Numbers

给定整数 $k$。存在一个由 $n$ 位二进制数构成的序列 $a_1,a_2,\dots,a_{2^k+1}$。其中 $a_1$ 与 $a_{2^k+1}$ 已知，其余位置数值未知。我们分 $k$ 轮按照如下规则填充所有未知数值： 第一，假设第 $i$ 轮开始前，已经填充完毕的下标为 $p_1 < p_2 < \dots < p_m$。第一轮开始前仅下标 $1,2^k+1$ 有数值。 第二，对每个 $j \in [1,m-1]$，执行赋值 $$ a_{\frac{p_j+p_{j+1}}{2}} := a_{p_j} \oplus a_{p_{j+1}} $$ 第三，所有赋值操作同时进行，操作完成后这些新下标也变为已填充状态。 可以证明，该过程一定能填满整个序列。 以 $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},\quad a_4 = a_3 \oplus a_5 = \texttt{010} $$ 你需要计算表达式： $$ x_1 y_1 + x_2 y_2 + \dots + x_{2^k+1} y_{2^k+1} $$ 其中 $x_i$ 表示 $a_i$ 中二进制位为 $\texttt{1}$ 的数量，$y_i$ 表示 $a_i$ 中二进制位为 $\texttt{0}$ 的数量。 注：$x \oplus y$ 表示两数按位异或。

本题包含多组测试数据。第一行输入整数 $t$，满足 $$ 1 \le t \le 10^4,\quad 1 \le n \le 10^5,\quad 1 \le k \le 30 $$ 代表测试数据组数。 每组测试数据描述如下： 第一行两个整数 $n,k$，分别代表二进制数的位数、控制序列长度的参数。 第二行输入长度为 $n$ 的二进制字符串 $s$，代表 $a_1$。 第三行输入长度为 $n$ 的二进制字符串 $z$，代表 $a_{2^k+1}$。 保证所有测试数据的 $n$ 之和不超过 $10^5$。

对每组测试用例，输出题目中表达式的计算结果。

第一组测试用例的填充过程已在题目描述中给出，最终序列为 $[\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} $$ 整个序列所有数均为 $0$，表达式结果为 $0$。