P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)

题目描述

给定长度为 $2^n$ 两个序列 $A,B$，设

分别当 $\oplus$ 是 or, and, xor 时求出 $C$。

输入格式

第一行，一个整数 $n$。
第二行，$2^n$ 个数 $A_0, A_1, \ldots, A_{2^n-1}$。
第三行，$2^n$ 个数 $B_0, B_1, \ldots, B_{2^n-1}$。

输出格式

三行，每行 $2^n$ 个数，分别代表 $\oplus$ 是 or, and, xor 时 $C_0, C_1, \ldots, C_{2^n-1}$ 的值 $\bmod\ 998244353$。

输入输出样例 #1

输入 #1

2
2 4 6 8
1 3 5 7

输出 #1

2 22 46 250
88 64 112 56
100 92 68 60

说明/提示

$1 \le n \le 17$。