$$c_i = \sum_{j \otimes k = i} a_j b_k= \sum_{0 \le k < 2^n} \sum_{0\le j < 2^n} [j \otimes k = i] a_j b_k$$ $$\ (\otimes \in \{\oplus,\lor,\land \})$$

$\mathrm{FWT}$可以用于解决上述的式子，其中 $\otimes$ 可以为二进制的逻辑运算如：异或、与、或。

集合并卷积（或卷积）

$$c_i = \sum_{j \lor k = i} a_j b_k= \sum_{0 \le k < 2^n} \sum_{0\le j < 2^n} [j \lor k = i] a_j b_k$$
定义： $$\hat{c}_i=\sum_{0 \le j \le i} c_j$$
所以： $$\hat{c}_i = \sum_{0 \le j < 2^n}\sum_{0\le k < 2^n}[j \lor k \le i]a_jb_k$$
$$\hat{c}_i = \sum_{0 \le j \le i}\sum_{0\le k \le i}a_jb_k=\Big( \sum_{0 \le j \le i}a_j\Big)\Big(\sum_{0\le k \le i}b_k\Big)=\hat{a}_j\hat{b}_k$$

---

集合交卷积（与卷积）

$$c_i = \sum_{j \land k = i} a_j b_k= \sum_{0 \le k < 2^n} \sum_{0\le j < 2^n} [j \land k = i] a_j b_k$$
定义： $$\hat{c}_i=\sum_{i \le j < 2^n} c_j$$
所以： $$\hat{c}_i =\sum_{0 \le j < 2^n}\sum_{0 \le k < 2^n}[j \land k \ge i]a_jb_k$$
$$\hat{c}_i = \sum_{i \le j < 2^n}\sum_{i \le k < 2^n}a_jb_k=\Big( \sum_{i \le j < 2^n}a_j\Big)\Big(\sum_{i \le k < 2^n}b_k\Big)=\hat{a}_j\hat{b}_k$$

---

FWT 包含 or,and,xor

#include <cstdio>
#include <cstring>
#define R register
const int Mod = 998244353, p = 2341;
int Pow(R int A, R int K)
{R int d = 1;while(K){if(K & 1) d = 1ll * d * A % Mod;K >>= 1;A = 1ll * A * A % Mod;}return d;
}
int a[1 << 20], b[1 << 20], c[1 << 20];
int main()
{R int n;scanf("%d", &n);for(R int i = 0; i < (1 << n); i++) scanf("%d", &a[i]);for(R int i = 0; i < (1 << n); i++) scanf("%d", &b[i]);R int t; scanf("%d", &t);if(t == 1){for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(!(j >> i & 1)){(a[j | 1 << i] += a[j]) %= Mod;(b[j | 1 << i] += b[j]) %= Mod;}for(R int i = 0; i < (1 << n); ++i) c[i] = 1ll * a[i] * b[i] % Mod;for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(!(j >> i & 1))(c[j | 1 << i] -= c[j] - Mod) %= Mod;/*      集合交卷积for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(j >> i & 1)f[j ^ 1 << i] += f[j];for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(j >> i & 1)g[j ^ 1 << i] += g[j];for(R int i = 0; i < (1 << n); ++i) h[i] = f[i] * g[i];for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(j >> i & 1)h[j ^ 1 << i] -= h[j];
*/}else{for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(!(j >> i & 1)){R int l = a[j], r = a[j | 1 << i];a[j] = (l + r) % Mod; a[j | 1 << i] = (Mod + l - r) % Mod;l = b[j], r = b[j | 1 << i];b[j] = (l + r) % Mod; b[j | 1 << i] = (Mod + l - r) % Mod;}for(R int i = 0; i < (1 << n); i++) c[i] = 1ll * a[i] * b[i] % Mod;for(R int i = 0; i < n; ++i)for(R int j = 0; j < (1 << n); ++j) if(!(j >> i & 1)){R int l = c[j], r = c[j | 1 << i];c[j] = (l + r) % Mod; c[j | 1 << i] = (Mod + l - r) % Mod;}for(R int j = 0, t = Pow(2, Mod - 1 - n); j < (1 << n); ++j) c[j] = 1ll * c[j] * t % Mod;}R int Ans = 0;for(R int i = 0; i < (1 << n); i++) Ans = (1ll * Ans * p + c[i]) % Mod;printf("%d", Ans);return 0;
}

---

FWT模板，包含or和xor，递归版

#include <cstdio>
#include <cstring>
#define R register
const int Mod = 998244353, p = 2341;
int a[1 << 20], b[1 << 20], c[1 << 20];
void FWTor(R int *A, R int l, R int r)
{if(r - l <= 1) return ;R int mid = l + r >> 1;FWTor(A, l, mid), FWTor(A, mid, r);for(R int i = l, j = mid; j < r; i++, j++) (A[j] += A[i]) %= Mod;
}
void unFWTor(R int *A, R int l, R int r)
{if(r - l <= 1) return ;R int mid = l + r >> 1;unFWTor(A, l, mid), unFWTor(A, mid, r);for(R int i = l, j = mid; j < r; i++, j++) (A[j] -= A[i] - Mod) %= Mod;
}
void FWTxor(R int *A, R int l, R int r)
{if(r - l <= 1) return ;R int mid = l + r >> 1;FWTxor(A, l, mid), FWTxor(A, mid, r);for(R int i = l, j = mid; j < r; i++, j++) {R int f = A[i], g = A[j];A[i] = (f + g) % Mod, A[j] = (f - g) % Mod;}
}
void unFWTxor(R int *A, R int l, R int r)
{if(r - l <= 1) return ;R int mid = l + r >> 1;unFWTxor(A, l, mid), unFWTxor(A, mid, r);for(R int i = l, j = mid; j < r; i++, j++) {R int f = A[i], g = A[j];A[i] = 1ll * (f + g)  * 499122177 % Mod, A[j] = 1ll * (f - g)  * 499122177 % Mod;}
}
int main()
{R int n;scanf("%d", &n);for(R int i = 0; i < (1 << n); i++) scanf("%d", &a[i]);for(R int i = 0; i < (1 << n); i++) scanf("%d", &b[i]);R int t; scanf("%d", &t);if(t == 1){FWTor(a, 0, 1 << n);FWTor(b, 0, 1 << n);for(R int i = 0; i < (1 << n); i++) c[i] = 1ll * a[i] * b[i] % Mod;unFWTor(c, 0, 1 << n);  }else{FWTxor(a, 0, 1 << n);FWTxor(b, 0, 1 << n);for(R int i = 0; i < (1 << n); i++) c[i] = 1ll * a[i] * b[i] % Mod;unFWTxor(c, 0, 1 << n);  }for(R int i = 0; i < (1 << n); i++) printf("%d ", c[i]); puts("");R int Ans = 0;for(R int i = 0; i < (1 << n); i++) Ans = (1ll * Ans * p + c[i]) % Mod;printf("%d", Ans);return 0;
}