Bitmask Transforms — SOS, Zeta, Möbius

Advanced transforms convert between value ↔ subset-sum domains; SOS is the entry point before full subset convolution theory.

Try this in Python

# After SOS zeta, f[mask] = sum_{submask ⊆ mask} raw[submask] (toy check n=2)
n = 2
raw = [0, 1, 2, 4]
f = raw[:]
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

• Same triple loop pattern as SOS; difference is what raw stores.
• Möbius inverts zeta to recover coefficients.
• Heavy theory—pair with a known template problem.