1. Full-Row Transitions vs. The Cell-by-Cell Broken Profile Frontier
Consider counting the number of ways to tile an $N \times M$ grid with $1 \times 2$ and $2 \times 1$ dominoes (ensure $M \le N$ by transposing the grid if $M > N$, so $M \le \sqrt{NM}$).
In a naive row-by-row Bitmask DP, transitioning from row $r-1$'s protrusion mask to row $r$'s protrusion mask requires enumerating all horizontal domino placements inside row $r$, costing $O((1 + \sqrt{2})^M)$ or $O(4^M)$ per row.
In Broken Profile DP, we process cells in reading order $(r, c)$. At the moment we stand at cell $(r, c)$, the frontier separating the already-processed prefix from the unprocessed suffix consists of exactly $M$ boundary cells:
- Cells $(r, 0), (r, 1), \dots, (r, c-1)$ in the current row $r$ (bits $0..c-1$ of
mask). - Cells $(r-1, c), (r-1, c+1), \dots, (r-1, M-1)$ in the previous row $r-1$ (bits $c..M-1$ of
mask).
Core Invariant — Broken Profile Bit Meaning at Cell $(r, c)$
In the $M$-bit profile mask before processing cell $(r, c)$:
- Bit $k$ ($k < c$) is $1$ iff cell $(r, k)$ is already covered (or protrudes downward).
- Bit $c$ is $1$ iff cell $(r-1, c)$ protrudes a vertical domino downward into $(r, c)$ (meaning $(r, c)$ is already covered from above!).
When processing $(r, c)$, we look at bit $c$ of mask:
1. If bit $c$ is $1$ ($(r, c)$ already covered from above): We cannot place a new domino starting at $(r, c)$; we simply clear bit $c$ (mask ^ (1 << c)) so $(r, c)$ does not protrude into $(r+1, c)$.
2. If bit $c$ is $0$ ($(r, c)$ is uncovered): We MUST cover $(r, c)$ in one of two ways:
- Vertical Domino $(r, c) \to (r+1, c)$: Set bit $c$ to $1$ (mask | (1 << c)), protruding into row $r+1$.
- Horizontal Domino $(r, c-1) \to (r, c)$: Alternatively (in the backward-looking convention where bit $0$ means covered and $1$ means uncovered, or looking at bit $c$ and $c+1$), if $c + 1 < M$ and bit $c+1$ is $0$ (cell $(r-1, c+1)$ doesn't protrude into $(r, c+1)$), place a horizontal domino covering $(r, c)$ and $(r, c+1)$ by setting bit $c+1$ to $1$ (mask | (1 << (c + 1))) so $(r, c+1)$ will be seen as covered when the loop steps to $c + 1$!
2. Visual Geometry of the Staircase Frontier
Row r, Cols 0 .. c-1"] --- Step["Step at Col c:
Cell (r, c) replaces (r-1, c)"] Step --- B1["Bits c .. M-1:
Row r-1, Cols c .. M-1"] end Grid --> Choice{"Is bit c set in mask?
(Already covered?)"} Choice -- "Yes (bit c == 1)" --> Clear["Clear bit c:
next_mask = mask ^ (1 << c)"] Choice -- "No (bit c == 0)" --> Place["1. Vertical: next_mask = mask | (1 << c)
2. Horizontal (if c+1 < M and bit c+1 == 0):
next_mask = mask | (1 << (c+1))"]
Hardware Reality — Always Transpose the Grid So $M = \min(R, C)$
Suppose a grid has $R = 12$ rows and $C = 100$ columns ($R \times C = 1200$). If you orient the profile along $C = 100$, $2^{100}$ is astronomically impossible. Because $R \times C \le 1200$ implies $\min(R, C) \le \lfloor \sqrt{1200} \rfloor = 34$ (and in typical tiling problems $R \le 12, C \le 1000$), transposing the grid so that $M = \min(R, C)$ is the width reduces $2^M$ to $2^{12} = 4096$, solving a $12 \times 1000$ grid in $12{,}000 \times 4096 \approx 4.9 \times 10^7$ simple integer additions (~25 milliseconds)!
3. Complexity Matrix
Trace dimension-by-dimension SOS DP bit-flips F[mask] += F[mask ^ (1<<i)] without overcounting, Broken Profile staircase wavefront domino tiling, and Digit DP tight-prefix automata.
Invariant & State
| Grid Tiling Method ($N \ge M$) | States Kept in Memory | Transitions / Step | Total Time Complexity | Time for $N=100, M=12$ |
|---|---|---|---|---|
| Naive Full-Row Matrix Transition | O(2^M) | O(2^M) | O(N * 4^M) | $\approx 1.6 \times 10^9$ ops (TLE) |
| Broken Profile (Cell-by-Cell Rolling) | O(2^M) | O(1) ($le 2$ choices) | O(N * M * 2^M) | $\approx 4.9 \times 10^6$ ops (3 ms) |
| Matrix Exponentiation on Profile (Huge $N$) | O(4^M) | Matrix-Matrix Mult | O(8^M log N) | Best when $M \le 7, N = 10^{18}$ |
| Kasteleyn's Pfaffian / Cosine Product Formula | O(1) | Closed-Form Cosine Sum | O(N * M) | Exact float/complex formula (no obstacles) |
4. Reference C++20 Implementation
#include <algorithm>
#include <cstdint>
#include <vector>
// Count ways to tile an N x M grid with 1x2 and 2x1 dominoes modulo 10^9 + 7 in O(N * M * 2^min(N, M))
long long count_domino_tilings_broken_profile(int n, int m) {
if ((1LL * n * m) % 2 != 0) return 0; // Odd number of cells cannot be tiled by dominoes!
if (m > n) std::swap(n, m); // Ensure M <= N so 2^M is tiny!
constexpr long long MOD = 1'000'000'007LL;
const int num_masks = 1 << m;
std::vector<long long> dp(num_masks, 0), next_dp(num_masks, 0);
dp[0] = 1; // Initially, no dominoes protrude into row 0
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
std::fill(next_dp.begin(), next_dp.end(), 0);
for (int mask = 0; mask < num_masks; ++mask) {
long long ways = dp[mask];
if (!ways) continue;
if ((mask >> c) & 1) {
// Cell (r, c) is already covered by a vertical domino from (r-1, c)
// or a horizontal domino from (r, c-1); clear bit c for row r+1
int nmask = mask ^ (1 << c);
next_dp[nmask] = (next_dp[nmask] + ways) % MOD;
} else {
// Option 1: Place a VERTICAL domino covering (r, c) and (r+1, c)
if (r + 1 < n) {
int nmask = mask | (1 << c);
next_dp[nmask] = (next_dp[nmask] + ways) % MOD;
}
// Option 2: Place a HORIZONTAL domino covering (r, c) and (r, c+1)
// Legal iff c + 1 < m AND cell (r, c+1) is not already covered from (r-1, c+1)
if (c + 1 < m && !((mask >> (c + 1)) & 1)) {
int nmask = mask | (1 << (c + 1));
next_dp[nmask] = (next_dp[nmask] + ways) % MOD;
}
}
}
std::swap(dp, next_dp);
}
}
return dp[0]; // After the last row, 0 dominoes may protrude past row n - 1
}Production Pitfall — Allowing Horizontal Dominoes to Wrap Around Row Boundaries ($c = M - 1 \to c = 0$)
When placing a horizontal domino at cell $(r, c)$ by setting bit $c + 1$ (mask | (1 << (c + 1))), you must guard with if (c + 1 < m)! Without that check, at the rightmost column $c = m - 1$, a horizontal domino would illegally wrap around the edge of the board or shift out of the $M$-bit mask. Similarly, if the grid contains blocked obstacle cells grid[r][c] == '#', an obstacle cell requires that bit $c$ is currently $0$ (no domino protruding into the obstacle) and transitions only to mask (leaving bit $c$ as $0$).