You've learned to use bitmasks as DP states. Now here's a different problem: given values , compute for each mask the sum of over all submasks of that mask. Example: if and mask (binary ), its submasks are (binary ).
You need the sum . The naive approach iterates all submasks for each mask. That's . With , that's billion operations. Too slow. SOS DP does it in , about million operations for .