Bitmask transform — SOS/Zeta/Möbius

Value ↔ subset-sum; SOS entry.

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

• SOS pattern; raw meaning.
• Möbius inverse.
• Template problems.