按位异或卷积（Bitwise XOR Convolution）

问题描述

给定两个长度为 $2^N$ 的整数序列
$a_0, a_1, \dots, a_{2^N-1}$ 和 $b_0, b_1, \dots, b_{2^N-1}$，
计算它们的按位异或卷积序列 $c_0, c_1, \dots, c_{2^N-1}$，定义为：

$$c_k = \sum_{\substack{i,j \\ i \oplus j = k}} a_i \cdot b_j \bmod 998244353,$$

其中 $i \oplus j$ 表示按位异或运算。

约束条件

• $0 \leq N \leq 20$
• $0 \leq a_i, b_i < 998244353$

输入格式

$N$
$a_0\ a_1\ \cdots\ a_{2^N-1}$
$b_0\ b_1\ \cdots\ b_{2^N-1}$

输出格式

$c_0\ c_1\ \cdots\ c_{2^N-1}$

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16

492 488 476 472 428 424 412 408