Challenge: Transition Enumeration

For each mask, enumerate all ways to fill the row. This is recursive: at each column, try placing or not placing. Recursive generator: $gen(col, curMask, nextMask)$ explores placing horizontal, vertical, or nothing at column $col$. improvement: precompute all valid (mask, nextMask) pairs.

Store in adjacency list. DP becomes matrix multiplication. For large $n$, small $m$: matrix exponentiation gives $O(4^m \cdot m \cdot \log n)$. Useful when $n >> 2^m$.