iii. Submasks, Supermasks and SOS DP

Iterating over subsets of subsets costs $3^n$. Aggregating over all subsets or supersets of every mask (zeta and Möbius transforms, “SOS DP”) costs $n{2}^n$. Know which one your transition really needs.

Enumeration

for (int s = m; s; s = (s - 1) & m) {}             // non-empty submasks of m, decreasing
for (int s = m; s < (1 << n); s = (s + 1) | m) {}   // supermasks of m within n bits, increasing

• s - 1 clears the lowest set bit and sets everything below it; & m keeps only bits of $m$. So the loop visits every submask exactly once.
• Over all masks: ${\sum }_m{2}^{|m|}={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=3^n$. Each element is in neither, in the mask only, or in both. $3^n$ is fine up to $n\approx 16$-$17$ ($3^{17}\approx 1.3\cdot 10^8$).

Proof: the submask loop and the $3^n$ bound

Enumeration. Let $s$ be a nonzero submask of $m$ (so $s=s\&m$). Write $s=h\cdot 2^{k+1}+2^k$ where $k=\mathrm{ctz}(s)$, so bit $k$ is the lowest set bit and $h$ is whatever sits above it. Then $s-1=h\cdot 2^{k+1}+(2^k-1)$: bit $k$ and all bits above are unchanged except bit $k$ itself drops to $0$, while bits $\mathrm{0..}k-1$ (all $0$ in $s$) become all $1$. ANDing with $m$ clears exactly the new low bits that $m$ doesn’t have, leaving the largest submask of $m$ strictly below $s$ in numeric value, and every bit of $m$ above position $k$ that was set in $s$ stays set (since $(s-1)\&m$ only touches the trailing run). So the sequence is strictly decreasing, every value produced is a submask of $m$ (since each step ANDs with $m$), and iterating until $0$ visits all of them: induction on $|s|$‘s position shows no submask is skipped, since the construction is just “take the current submask, clear its lowest set bit, and re-fill every lower bit of $m$” which is exactly the predecessor of $s$ in the submask poset ordered by value. $3^n$ bound. ${\sum }_m{2}^{|m|}$ sums, for every mask $m$, the number of its submasks. Group by which of the $3$ states each of the $n$ elements is in relative to $(m,s)$: not in $m$ (so not in $s$ either), in $m$ but not in $s$, or in both $m$ and $s$ — these $3$ independent choices per element, over $n$ elements, give $3^n$ total $(m,s)$ pairs with $s\subseteq m$, matching ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=3^n$ by the binomial theorem applied to $(1+2{)}^n$. $■$

Tested: the submask-enumeration loop was checked against a direct scan of all $2^n$ masks (confirming every submask of every $m$ is visited exactly once, non-submasks never visited) for $n$ up to 6.

• Fixed popcount (all $k$-subsets in increasing order): Gosper’s hack, $c=v\&-v$, $r=v+c$, $v^{\prime }=r\mid (((v\oplus r)\gg 2)/c)$. Handle $k=0$ as a separate base case (there’s no lowest set bit to use), and stop before $r$ would need a bit beyond the $n$-bit universe (don’t build 1 << n when $n$ equals the type width).

Set partition DP in $O(3^n)$:

dp[0] = 0;
for (int m = 1; m < 1 << n; m++) {
    int low = m & -m;                         // fix the block containing the lowest element
    for (int s = m; s; s = (s - 1) & m)
        if ((s & low) && ok[s]) dp[m] = min(dp[m], dp[m ^ s] + cost[s]);
}

Fixing the lowest element avoids counting the same partition in every block order: for counting, it’s required; for optimisation it’s a $\sim k!$ speedup.

Zeta and Möbius transforms

$\hat{f}(S)={\sum }_{T\subseteq S}f(T)\text{(subset sum)},\check{f}(S)={\sum }_{T\supseteq S}f(T)\text{(superset sum)}.$

for (int i = 0; i < n; i++) for (int m = 0; m < 1 << n; m++)
    if (m >> i & 1) f[m] += f[m ^ 1 << i];          // subset zeta; use -= for Möbius (inverse)
for (int i = 0; i < n; i++) for (int m = 0; m < 1 << n; m++)
    if (!(m >> i & 1)) f[m] += f[m | 1 << i];       // superset zeta; -= for inverse

The bit loop must be outside: it’s an $n$-dimensional prefix sum with every dimension of size 2. The inverse is

$f(S)={\sum }_{T\subseteq S}(-1{)}^{|S\setminus T|}\hat{f}(T),$

which is inclusion-exclusion over a subset lattice. Any “aggregate over submasks” with an idempotent or invertible operation works the same way: max, min, gcd, OR of bitsets, counting.

Proof: the zeta transform and its Möbius inverse

Zeta correctness. Process bits $0,\dots ,n-1$ in order; let $F^{(i)}$ be the array after processing bits $\mathrm{0..}i-1$. Claim: $F^{(i)}[m]={\sum }_{T}f(T)$ over all $T$ that agree with $m$ on bits $\ge i$ and are an arbitrary subset of $m$‘s bits below $i$. Base case $i=0$: $F^{(0)}=f$, and the only ”$T$ agreeing on bits $\ge 0$ with no freedom below” is $T=m$ itself — matches. Inductive step: processing bit $i$ does if m has bit i: F[m] += F[m without bit i]. If $m$ lacks bit $i$, $F^{(i+1)}[m]=F^{(i)}[m]$, consistent (no new freedom is gained since bit $i$ of every valid $T$ must also be $0$). If $m$ has bit $i$, $F^{(i+1)}[m]=F^{(i)}[m]+F^{(i)}[m\oplus 2^i]$, which by the inductive hypothesis sums $f(T)$ over $T$‘s that already had the right freedom below $i$ and either keep bit $i$ set (the first term) or clear it (the second, since $m\oplus 2^i$ agrees with $m$ above bit $i$, and the inductive hypothesis for mask $m\oplus 2^i$ ranges $T$ over subsets agreeing on bits $>i$, i.e. exactly $m$‘s bits above $i$, with bit $i$ cleared) — together giving exactly ”$T$ agrees with $m$ on bits $>i$, arbitrary on bits $\le i$”. After all $n$ bits, $F^{(n)}[m]={\sum }_{T\subseteq m}f(T)=\hat{f}(m)$. Möbius inverse. Running the same dimension-sweep with subtraction instead of addition is literally the signed inclusion-exclusion sum: by induction the same argument shows after processing bit $i$ with subtraction, the array equals ${\sum }_T(-1{)}^{|\{j<i:T_j\ne m_j\}|}\hat{f}(T)$ restricted appropriately, and after all $n$ bits this is exactly ${\sum }_{T\subseteq S}(-1{)}^{|S\setminus T|}\hat{f}(T)$, which recovers $f(S)$ because substituting $\hat{f}(T)={\sum }_{U\subseteq T}f(U)$ and swapping summation order gives ${\sum }_{U\subseteq S}f(U){\sum }_{U\subseteq T\subseteq S}(-1{)}^{|S\setminus T|}$, and the inner sum is $0$ unless $U=S$ (it’s $(1-1{)}^{|S\setminus U|}$ by the binomial theorem, which is $0$ for $|S\setminus U|>0$ and $1$ for $U=S$). $■$

Tested against a direct $O(4^n)$ double loop over all $(m,T)$ pairs with $T\subseteq m$, confirming both the forward zeta transform and that applying the subtractive sweep to its output recovers the original array exactly, for $n$ up to 6.

Convolutions over the subset lattice

Want $h(S)$	Method	Cost
${\sum }_{A\cup B=S}f(A)g(B)$ (OR)	subset zeta both, multiply pointwise, Möbius	$O(n{2}^n)$
${\sum }_{A\cap B=S}f(A)g(B)$ (AND)	superset zeta, multiply, inverse	$O(n{2}^n)$
${\sum }_{A\oplus B=S}f(A)g(B)$ (XOR)	Walsh-Hadamard (Bitwise Convolutions)	$O(n{2}^n)$
${\sum }_{A\bigsqcup B=S}f(A)g(B)$ (disjoint union)	subset convolution (ranked zeta)	$O(n^2{2}^n)$

Applications

Problem	Technique
for each mask, count array elements that are submasks of it	subset zeta over the frequency array
count pairs $a_i\&a_j=0$	for each $a_i$, count elements that are submasks of $\overline{a_i}$
count pairs with $a_i\mid a_j=$ full set	superset zeta, or Möbius trick
count subsets of the array whose AND is exactly $x$	$g(x)=2^{\check{c}(x)}-1$ counts subsets whose AND is a supermask of $x$; superset Möbius gives exactly $x$
subsets with OR exactly $x$	$2^{\hat{c}(x)}$ then subset Möbius
max $f(A)+g(B)$ with $A\cap B=\varnothing$	best of $g$ over submasks of $\overline{A}$ (max-zeta)
for each mask, the two best values over its submasks (from distinct sources)	zeta with “top two” merge
inclusion-exclusion over $n\le 20$ conditions	Möbius on counts of “violates at least $S$“
number of $k$-colourings / chromatic number of a graph with $n\le 20$	$\chi \le k$ iff $\sum_{S}(-1)^{n-
merge two sub-results at a shared vertex (small-universe Steiner tree)	subset-sum DP over the terminal set, via subset zeta/Möbius (Steiner Tree)
TSP / routing with cities grouped into $\le 20$ groups, set cover, exact cover	$3^n$ split DP, or subset convolution when the transition is a disjoint split (Exact Cover)
counting matchings in a small graph	split off one vertex’s partner, sum over the rest as a subset transition
minimal covering superset of $m$ satisfying a property $P$	enumerate supermasks of $m$ in increasing numeric order and stop at the first hit — note increasing numeric order is not increasing popcount order, so for smallest cardinality sort by popcount or BFS the mask lattice instead
requirement closure (“if you take these, you must also take those”)	supermask enumeration is the natural iteration order for the closure computation

The chromatic number trick (Björklund-Husfeldt-Koivisto) is worth remembering: compute $i(S)$ for all $S$ with a zeta transform of the “is independent” indicator, then test $k=1,2,\dots$. Do it modulo a random prime to avoid big numbers (small chance of a false negative).

Subset convolution and set power series

Disjoint union is $|A|+|B|=|S|$ together with $A\cup B=S$. Split by popcount rank:

1. ${\hat{f}}_k(S)=f(S)[|S|=k]$, and the same for $g$; zeta-transform each rank.
2. ${\hat{h}}_k={\sum }_{i+j=k}{\hat{f}}_i\cdot {\hat{g}}_j$ pointwise.
3. Möbius-transform each ${\hat{h}}_k$ and read $h(S)={\hat{h}}_{|S|}(S)$.

Proof: ranked zeta/Möbius computes the disjoint-union convolution

By the zeta-transform proof above, $({\hat{f}}_k{)}^{\wedge }(S)={\sum }_{T\subseteq S}{\hat{f}}_k(T)={\sum }_{T\subseteq S,|T|=k}f(T)$ — the sum of $f$ over rank-$k$ subsets of $S$. The pointwise product $({\hat{f}}_i{)}^{\wedge }(S)\cdot ({\hat{g}}_j{)}^{\wedge }(S)=({\sum }_{A\subseteq S,|A|=i}f(A))({\sum }_{B\subseteq S,|B|=j}g(B))={\sum }_{A,B\subseteq S,|A|=i,|B|=j}f(A)g(B)$, summing over all pairs $A,B\subseteq S$ of the given ranks, overlapping or not. Summing over $i+j=k$ and Möbius-inverting back from $S$-indexed sums to “exactly $S$” (same inclusion-exclusion as the plain Möbius inverse, applied separately within rank $k$) gives ${\hat{h}}_k(S)={\sum }_{A,B\subseteq S,|A|=i,|B|=j,i+j=k,A\cup B=S}f(A)g(B)$. Restricting to $A\cup B=S$ with $|A|+|B|=|S|=k$ forces $A\cap B=\varnothing$ (if some element were in both, $|A\cup B|<|A|+|B|$, contradicting $|A\cup B|=|S|=|A|+|B|$), and conversely every disjoint pair with $A\bigsqcup B=S$ has $A\cup B=S$ and $|A|+|B|=|S|$. So reading off $h(S)={\hat{h}}_{|S|}(S)$ gives exactly ${\sum }_{A\bigsqcup B=S}f(A)g(B)$, the disjoint-union convolution, with no overlap terms surviving. $■$

Tested subsetConv against a direct $O(3^n)$ brute force enumerating every disjoint split of every $S$, for $n$ up to 6, random integer arrays — all match.

// a, b: size 2^n, values mod p. Ranked arrays use O(n 2^n) memory: use 32-bit modints.
vector<mint> subsetConv(const vector<mint>& a, const vector<mint>& b, int n) {
    int N = 1 << n;
    vector<vector<mint>> A(n + 1, vector<mint>(N)), B = A, C = A;
    for (int s = 0; s < N; s++) A[popcount((unsigned)s)][s] = a[s], B[popcount((unsigned)s)][s] = b[s];
    auto zeta = [&](vector<mint>& f, bool inv) {
        for (int i = 0; i < n; i++) for (int s = 0; s < N; s++)
            if (s >> i & 1) inv ? f[s] -= f[s ^ 1 << i] : f[s] += f[s ^ 1 << i];
    };
    for (int k = 0; k <= n; k++) zeta(A[k], 0), zeta(B[k], 0);
    for (int k = 0; k <= n; k++) for (int i = 0; i <= k; i++)
        for (int s = 0; s < N; s++) C[k][s] += A[i][s] * B[k - i][s];
    vector<mint> c(N);
    for (int k = 0; k <= n; k++) zeta(C[k], 1);
    for (int s = 0; s < N; s++) c[s] = C[popcount((unsigned)s)][s];
    return c;
}

In the ranked (zeta) domain each mask holds a polynomial in the rank variable of degree $\le n$, and subset convolution is polynomial multiplication there. So exp and log of set power series are pointwise polynomial exp/log of degree $n$ (with $f(\varnothing )=0$ for exp), $O(n^2{2}^n)$:

• connected graphs on vertex set $S$ ($n\le 20$): $\log$ of “all graphs on $S$” ($2^{e(S)}$), or any other “connected structures = log(all structures)” relation;
• set partitions into blocks with weights: $\exp$ of the block weights;
• number of spanning forests / connected spanning subgraphs on small vertex sets.