在算法竞赛中，FWT 是用于解决对下标进行位运算卷积问题的方法。
公式：
1.i=j|k(j,k相或等于i)
void Or(ll * a, ll type) { // 迭代实现，常数更小
for (ll x = 2; x <= n; x <<= 1) {
ll k = x >> 1;
for (ll i = 0; i < n; i += x) {
for (ll j = 0; j < k; j++) {
(a[i + j + k] += a[i + j] * type) %= P;
}
}
}
}
2.i=j&k(j,k相与等于i)
void And(ll * a, ll type) {
for (ll x = 2; x <= n; x <<= 1) {
ll k = x >> 1;
for (ll i = 0; i < n; i += x) {
for (ll j = 0; j < k; j++) {
(a[i + j] += a[i + j + k] * type) %= P;
}
}
}
}
3.i=j^k
void fwt(LL a[], int n, int v) {
for (int d = 1; d < n; d <<= 1) {
for (int m = d << 1, i = 0; i < n; i += m) {
for (int j = 0; j < d; j++) {
LL x = a[i + j], y = a[i + j + d];
if (v == 1) a[i + j] = (x + y), a[i + j + d] = (x - y);
else a[i + j] = (x + y) / 2, a[i + j + d] = (x - y) / 2;
}
}
}
}
