Sum Over Subsets (SOS) DP — Zeta on Masks

For each mask, aggregate over all submasks in O(n 2^n) using DP over bits—foundation for many subset convolutions.

Try this in Python

n = 3
f = [i for i in range(1 << n)]
for i in range(n):
    for mask in range(1 << n):
        if (mask >> i) & 1:
            f[mask] += f[mask ^ (1 << i)]
print(f)

Key takeaways

• This is the zeta transform on subset lattice.
• Reverse loops give Möbius/inclusion inversion patterns.
• Combine with modulo and NTT only when problem requires.