\[C_k = \sum_{i|j=k}A_i B_j \]
这样的或卷积可以做一次 \(\text{FWT}\)，把数组变为 \(a_i = \sum_{j\subseteq i}A_i\)，也就是子集和的形式，然后就可以对应位相乘了
变回去的话就减掉之前加上来的贡献
与卷积，异或卷积同理
$\text{Code}$
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define IN inline
using namespace std;
template <typename T>
IN void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
typedef long long LL;
const int N = 2e5 + 5, P = 998244353, inv2 = (P + 1) >> 1;
int A[N], B[N], a[N], b[N], n;
IN void init(){for(int i = 0; i < n; i++) a[i] = A[i], b[i] = B[i];}
IN void print(){for(int i = 0; i < n; i++) printf("%d ", a[i]); puts("");}
IN void mul(){for(int i = 0; i < n; i++) a[i] = (LL)a[i] * b[i] % P;}
IN void FWT_or(int *a, int op) {
for(int mid = 1; mid < n; mid <<= 1)
for(int i = 0; i < n; i += (mid << 1))
for(int j = 0; j < mid; ++j)
(a[i + j + mid] += (LL)a[i + j] * op % P) %= P;
}
IN void FWT_and(int *a, int op) {
for(int mid = 1; mid < n; mid <<= 1)
for(int i = 0; i < n; i += (mid << 1))
for(int j = 0; j < mid; ++j)
(a[i + j] += (LL)a[i + j + mid] * op % P) %= P;
}
IN void FWT_xor(int *a, int op) {
for(int mid = 1; mid < n; mid <<= 1)
for(int i = 0; i < n; i += (mid << 1))
for(int j = 0; j < mid; ++j) {
int x = a[i + j], y = a[i + j + mid];
a[i + j] = (LL)(x + y) * op % P,
a[i + j + mid] = (LL)(x - y + P) * op % P;
}
}
int main() {
read(n), n = 1 << n;
for(int i = 0; i < n; ++i) read(A[i]);
for(int i = 0; i < n; ++i) read(B[i]);
init(), FWT_or(a, 1), FWT_or(b, 1), mul(), FWT_or(a, P - 1), print();
init(), FWT_and(a, 1), FWT_and(b, 1), mul(), FWT_and(a, P - 1), print();
init(), FWT_xor(a, 1), FWT_xor(b, 1), mul(), FWT_xor(a, inv2), print();
}