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

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

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

题目描述

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

Ci=∑j⊕k=iAj×BkC_i=\sum_{j\oplus k = i}A_j \times B_k

分别当 ⊕\oplus 是 or, and, xor 时求出 CC。

输入格式

第一行,一个整数 nn。
第二行,2n2^n 个数 A0,A1,…,A2n−1A_0, A_1, \ldots, A_{2^n-1}。
第三行,2n2^n 个数 B0,B1,…,B2n−1B_0, B_1, \ldots, B_{2^n-1}。

输出格式

三行,每行 2n2^n 个数,分别代表 ⊕\oplus 是 or, and, xor 时 C0,C1,…,C2n−1C_0, C_1, \ldots, C_{2^n-1} 的值  mod  998244353\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≤n≤171 \le n \le 17。