Sum Over Subsets (SOS) DP & Fast Walsh-Hadamard Transform (FWHT) for Bitwise Convolutions

1. From $O(3^N)$ Submasks to $O(N \cdot 2^N)$ Hypercube Prefix Sums (SOS DP)

Given an array $A[0..2^N - 1]$, we want to compute the Submask Zeta Transform (Sum Over Subsets) for every mask $m$:

Think of an $N$-bit integer $m$ not as a scalar, but as an $N$-tuple of coordinates $(b_{N-1}, \dots, b_1, b_0) \in \{0, 1\}^N$. Then $s \subseteq m$ simply means $s_i \le m_i$ in every coordinate $i \in \{0..N-1\}$—so $F[m]$ is literally an $N$-dimensional prefix sum over a $\underbrace{2 \times 2 \times \dots \times 2}_{N}$ grid!

2. Bitwise Convolutions (OR, AND, XOR) via Fast Walsh-Hadamard Transform (FWHT)

Suppose we want to compute the bitwise convolution $C[k] = \sum_{i \circledast j = k} A[i] \cdot B[j]$ for $\circledast \in \{|, \&, \oplus\}$ in $O(N \cdot 2^N)$ instead of $O(4^N)$:

• Bitwise OR Convolution ($i \mathbin{|} j = k$): Notice $(i \mathbin{|} j) \subseteq k \iff i \subseteq k \text{ and } j \subseteq k$. Therefore, the Submask Zeta Transform turns OR-convolution into pointwise multiplication: $\hat{C}[m] = \hat{A}[m] \cdot \hat{B}[m]$, followed by Fast Möbius Inversion (subtracting dp[m ^ (1 << i)])!
• Bitwise AND Convolution ($i \mathbin{\&} j = k$): $(i \mathbin{\&} j) \supseteq k \iff i \supseteq k \text{ and } j \supseteq k$. Use the Supermask Zeta Transform (when bit $i$ of $m$ is $0$, add dp[m | (1 << i)]), multiply pointwise, and invert by subtracting!
• Bitwise XOR Convolution ($i \oplus j = k$): Apply the Fast Walsh-Hadamard Transform (FWHT)—an $N$-dimensional size-2 DFT with butterfly $(u, v) \leftarrow (u + v,\; u - v)$—multiply pointwise, and apply the inverse butterfly $(u, v) \leftarrow ((u + v)/2,\; (u - v)/2)$!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <cstdint>
#include <vector>

// 1. Branchless In-Place Sum Over Subsets (Fast Zeta) & Inverse (Fast Mobius) in O(N * 2^N)
// invert = false: F[m] = sum_{s subseteq m} A[s]
// invert = true:  Recovers A[m] from F[m] via Inclusion-Exclusion
void sos_submask_transform(std::vector<long long>& f, int n, bool invert = false) {
    const int total = 1 << n;
    for (int i = 0; i < n; ++i) {
        const int half = 1 << i;
        const int step = half << 1;
        // Branchless butterfly: skips all masks where bit i is 0 without an if!
        for (int base = 0; base < total; base += step) {
            for (int j = 0; j < half; ++j) {
                if (!invert) {
                    f[base + half + j] += f[base + j];
                } else {
                    f[base + half + j] -= f[base + j];
                }
            }
        }
    }
}

// 2. Bitwise OR Convolution: C[k] = sum_{i | j == k} A[i] * B[j] in O(N * 2^N)
std::vector<long long> bitwise_or_convolution(std::vector<long long> a, std::vector<long long> b, int n) {
    sos_submask_transform(a, n, false);
    sos_submask_transform(b, n, false);
    for (int m = 0; m < (1 << n); ++m) a[m] *= b[m];
    sos_submask_transform(a, n, true); // Fast Mobius Inversion recovers exact OR-convolution!
    return a;
}

// 3. Fast Walsh-Hadamard Transform (FWHT) for Bitwise XOR Convolution: C[k] = sum_{i ^ j == k} A[i] * B[j]
void fwht_xor(std::vector<long long>& a, int n, bool invert = false) {
    const int total = 1 << n;
    for (int i = 0; i < n; ++i) {
        const int half = 1 << i;
        const int step = half << 1;
        for (int base = 0; base < total; base += step) {
            for (int j = 0; j < half; ++j) {
                long long u = a[base + j];
                long long v = a[base + half + j];
                a[base + j] = u + v;
                a[base + half + j] = u - v;
            }
        }
    }
    if (invert) {
        for (long long& x : a) x >>= n; // Divide by 2^n
    }
}