FWT 优化 n^2 位运算

所有如下代码的计算过程，都可以用 FWT 优化到 $nlogn$

int ans = 0;
int M = bitmask; // 统计所有满足 (i & j) == M 的 a[i] * b[j] 之和
for (int i = 0; i < (1 << n); i++) {
  for (int j = 0; j < (1 << n); j++) {
    if ((j & i) == M) {
      ans += a[i] * b[j];
        }
  }
}

优化：

void Or(vector<i64>& a, int type) {
    int n = a.size();
    for (i64 x = 2; x <= n; x <<= 1) {
        i64 k = x >> 1;
        for (i64 i = 0; i < n; i += x) {
            for (i64 j = 0; j < k; j++) {
                a[i + j + k] += a[i + j] * type;
            }
        }
    }
}

i64 cal(vector<i64> a, vector<i64> b) {

    // 正变换
    Or(a, 1);
    Or(b, 1);

    // 计算
    int M = a.size();
    vector<i64> c(M);
    for (int i = 0; i < M; ++i) {
        c[i] = a[i] * b[i];
    }

    // 逆变换
    Or(c, -1);
    return c[M - 1];
}

与和异或也一样：

void And(i64 *a, i64 type) {
    for (i64 x = 2; x <= n; x <<= 1) {
        i64 k = x >> 1;
        for (i64 i = 0; i < n; i += x) {
            for (i64 j = 0; j < k; j++) {
                a[i + j] += a[i + j + k] * type;
            }
        }
    }
}

void Xor(i64 *a, i64 type) {
    for (i64 x = 2; x <= n; x <<= 1) {
        i64 k = x >> 1;
        for (i64 i = 0; i < n; i += x) {
            for (i64 j = 0; j < k; j++) {
                a[i + j] += a[i + j + k];
                a[i + j + k] = a[i + j] - a[i + j + k] * 2;
                a[i + j] *= type;
                a[i + j + k] *= type;
            }
        }
    }
}