SOS DP — zeta

ஒவ்வொரு mask-க்கும் submask aggregate; O(n 2^n).

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

• Zeta transform.
• Reverse — Möbius.
• Modulo / NTT when needed.