子集卷积

【题目描述】

给定大小为 $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}$，并将其对 $998244353$ 取模后输出。

其中 $i \And j, i | j$ 分别表示按位与、按位或。

【输入】

第一行包含一个整数 $N$，接下来两行依次给出序列 $a$ 与 $b$。

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

【输出】

输出一行，包含所求的序列 $c$。

$c_0$ $c_1$ ... $c_{2^N - 1}$

【输入样例】

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

【输出样例】

9 28 38 100 58 144 172 408

【数据范围】

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

【来源】

Library Checker（yosupo06） subset_convolution