← 返回题目列表

Codeforces · 1034/E

E. 小C爱3 III

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

小C非常喜欢数字《3》。他喜欢与它有关的一切。

现在他对以下问题感兴趣:

有两个 $$$2^n$$$ 整数数组 $$$a_0,a_1,...,a_{2^n-1}$$$ 和 $$$b_0,b_1,...,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$$$,其中“$$$|$$$”表示按位或运算,“$$$\&$$$”表示按位与运算)。

令人惊讶的是,可以证明确实存在 $$$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)$$$。

第二行在 $$$[0,3]$$$ 中包含 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$a_{i-1}$$$。

第三行在 $$$[0,3]$$$ 中包含 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$b_{i-1}$$$。

输出

打印一行包含 $$$[0,3]$$$ 中的 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$c_{i-1}\&3$$$。 (很明显$$$c_{i}\&3$$$在$$$[0,3]$$$中)。

示例

输入 #1

1
11
11

输出 #1

12

输入 #2

2
0123
3210

输出 #2

0322