Sum over Subsets DP — Dimension-by-Dimension Bit Relaxation

F[mask] = Σ A[sub] over all submasks sub ⊆ mask. Watch the SOS DP sweep one bit at a time: each mask with bit i set pulls the value of mask with bit i cleared.

step 0

Bitmask grid — current array F

Pass for bit 0.
bit i set source: mask without bit i destination: mask += source

What is happening

Each pass sweeps one bit dimension. A destination mask absorbs the value of its bit-cleared (or bit-set) neighbor.
Press Step to begin. We start with F = A, then sweep bits 0, 1, …, n−1. After the last bit, every cell holds the full sum over its submasks.
Self-contained visualization. Counting semiring (+); entries are exact subset sums (no modulus needed at these sizes). Subset direction: mask with bit i set does F[mask] += F[mask ^ (1<<i)]. Superset direction: mask with bit i clear does F[mask] += F[mask | (1<<i)]. See junior.md and professional.md for the induction proof that the bit sweep computes the zeta transform in O(n · 2ⁿ).

How to read the grid. Each cell is one mask, labelled with its bits (e.g. 011) and its current value of F[mask]. During a pass for bit i, cells that have bit i set (subset mode) or clear (superset mode) are tinted blue; the amber cell is the source being read and the green cell is the destination being updated.
Why the empty mask never changes. Mask 000 has no bits set, so in the subset sweep it is never a destination — it keeps its original value A[0] throughout, and A[0] flows into every other cell.
Try this. Pick the "indicator at full mask" data and the subset direction: only the full mask starts at 1, and you will watch that 1 propagate down to all of its submasks — a direct picture of "which cells the full mask is a submask-summand of".