CF1034E Little C Loves 3 III

小 C 非常喜欢数字「3」。他喜欢所有与 3 有关的事物。 现在他对如下问题产生了兴趣： 有两个长度为 $2^n$ 的整数数组 $a_0,a_1,\ldots,a_{2^n-1}$ 和 $b_0,b_1,\ldots,b_{2^n-1}$。 任务是对于每个 $i\ (0 \leq i \leq 2^n-1)$，计算 $c_i = \sum a_j \cdot b_k$（其中 $j|k=i$ 且 $j\&k=0$，这里「$|$」表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)、「$\&$」表示[按位与运算](https://en.wikipedia.org/wiki/Bitwise_operation#AND)）。 令人惊奇的是，可以证明恰好有 $3^n$ 个三元组 $(i,j,k)$ 满足 $j|k=i$，$j\&k=0$ 且 $0 \leq i,j,k \leq 2^n-1$。因此小 C 想要优雅地解决这个与 $3$ 密切相关的优秀问题。 请你帮助他计算所有的 $c_i$。小 C 非常喜欢 $3$，所以他只想知道每个 $c_i\&3$ 的值。

第一行包含一个整数 $n\ (0 \leq n \leq 21)$。 第二行包含 $2^n$ 个 $[0,3]$ 范围内的整数，且没有空格——第 $i$ 个数字是 $a_{i-1}$。 第三行包含 $2^n$ 个 $[0,3]$ 范围内的整数，且没有空格——第 $i$ 个数字是 $b_{i-1}$。

输出一行，包含 $2^n$ 个 $[0,3]$ 范围内的整数，且没有空格——第 $i$ 个数字是 $c_{i-1}\&3$。（显然 $c_i\&3$ 一定在 $[0,3]$ 范围内。）

由 ChatGPT 4.1 翻译