P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)题解
P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)
题目描述
给定长度为 2n2^n2n 两个序列 A,BA,BA,B，设
Ci=∑j⊕k=iAj×BkC_i=sum_{joplus k = i}A_j imes B_kCi=j⊕k=i∑Aj×Bk
分别当 ⊕oplus⊕ 是 or, and, xor 时求出 CCC。
输入格式
第一行，一个整数 nnn。
第二行，2n2^n2n 个数 A0,A1,…,A2n−1A_0, A_1, ldots, A_{2^n-1}A0,A1,…,A2n−1。
第三行，2n2^n2n 个数 B0,B1,…,B2n−1B_0, B_1, ldots, B_{2^n-1}B0,B1,…,B2n−1。
输出格式
三行，每行 2n2^n2n 个数，分别代表 ⊕oplus⊕ 是 or, and, xor 时 C0,C1,…,C2n−1C_0, C_1, ldots, C_{2^n-1}C0,C1,…,C2n−1 的值 mod 998244353mod 998244353mod 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 171≤n≤17。
思路
模板题，直接写即可。
代码见下
#include
