⚙️AlgorithmAdvanced

Broken Profile DP

Key Points

•
Broken Profile DP is a dynamic programming technique that sweeps a grid one cell or one column at a time while encoding the boundary between processed and unprocessed cells as a compact state.
•
The state is typically a bitmask or a base-3 (ternary) encoding that records which boundary cells are 'open' (need to be matched/continued) and how they should connect.
•
It excels at hard tiling and path problems on grids, like counting domino tilings or Hamiltonian paths/cycles in small-width grids.
•
The time complexity usually looks like O(H · S(W) · T(W)) where S(W) is the number of boundary states (often 2^{W} or 3^{W}) and T(W) is the per-state transition cost.
•
Thinking of the DP as a 'bulldozer' pushing a vertical (or horizontal) frontier helps: the state records what sticks out of the bulldozer blade.
•
For tilings, a simple bitmask per column (2^{W} states) often suffices; for connectivity-constrained problems (like Hamiltonian paths), you need richer 'plug' encodings (≈3^{W}).
•
Careful state normalization and consistent cell ordering are crucial to avoid double counting or missing valid configurations.
•
Memory can be managed with rolling hash maps or vectors keyed by states so only the current frontier’s DP layer is kept.

Prerequisites

→Bitmask DP — Frontier states are encoded as bitmasks or small-base digits; comfort with bit operations is essential.
→Graph theory basics — Tiling and path problems are graph problems on grid graphs; degrees, paths, and cycles motivate the state design.
→Dynamic Programming — Broken profile DP is a specialized DP; understanding standard DP recurrences and rolling arrays is required.
→Combinatorics and counting — Many tasks ask for the number of configurations; understanding counting principles and modulo arithmetic helps.
→Balanced parentheses and Catalan numbers — Plug DP states for connectivity resemble balanced matchings; Catalan structures explain state counts.

Detailed Explanation

Tap terms for definitions

01Overview

Broken Profile DP is a powerful dynamic programming pattern for solving grid problems where decisions at one cell affect future cells in structured ways. Instead of storing the entire partial solution, we keep a compact description of just the 'frontier' between processed and unprocessed cells—this is the profile. We advance through the grid (cell-by-cell or column-by-column). The profile records dangling requirements such as unmatched domino halves, ongoing paths that must be continued, or degrees that vertices must attain. Because only a boundary of width W is tracked, the number of possible boundary descriptions is exponential in W but independent of the grid height H. This separation makes the method practical for long skinny grids. The simplest form uses a bitmask where 1 means "this position on the frontier has a pending piece from above (or left)". For more involved connectivity constraints (e.g., Hamiltonian paths/cycles), we upgrade the bitmask to a richer labeling (often ternary digits or small labels with parentheses-like pairing) so the DP can track which dangling ends must connect later without creating illegal early cycles. The technique is also known as profile DP, plug DP, or frontier-based DP (and is the DP analogue of transfer-matrix methods in combinatorics).

02Intuition & Analogies

Imagine clearing snow from a long sidewalk with a straight snowplow blade. As you push the blade forward, some snow spills over the edge of the blade and must be handled in the next step. In Broken Profile DP, the plow blade is the frontier between the cleared (processed) and uncleared (unprocessed) part of the grid. The 'spilled snow' is the information you must carry: maybe a domino half hanging into the next column, or one end of a path that hasn’t yet found its partner. Instead of remembering the full history of cleared cells, we summarize only what matters along the blade. For domino tilings, the summary might be a W-bit mask (for a grid of width W) indicating where a vertical domino sticks down into the next row. When we move to the next cell, we decide how to place dominos at that cell and update the mask accordingly. For Hamiltonian paths/cycles, think of colored strings crossing the blade; each string has two ends that must ultimately be connected to form one single path (or a cycle). If we assign a 'left bracket' to one end and a 'right bracket' to the matching other end, the frontier state naturally looks like a balanced-parentheses word. As the blade moves, we either extend strings, merge two strings, or start a new short arc—always making sure the nesting remains noncrossing. This visualization explains why the number of states depends on width only and why the count often grows like 2^{W} or 3^{W}: each position along the blade can be empty or carry a small amount of local information.

03Formal Definition

Let a grid be processed in a fixed order (e.g., row-major). Define a frontier F that separates processed cells P from unprocessed cells U. A Broken Profile DP maintains a function DP[i, s] where i is the index of the current position (cell or column), and s is a profile state describing necessary boundary conditions along F. The state s is usually a tuple s = (

s_{1}

s_{2}

, ...,

s_{W}

) where each

s_{j}

belongs to a small alphabet: for tilings,

s_{j}

∈ {0,1} meaning 'no pending tile' or 'pending vertical domino'; for connectivity,

s_{j}

∈ {0,1,2} or small labels indicating how dangling ends are paired. The transition function takes DP[i, s] and enumerates legal placements affecting the current frontier cell(s), producing new states s' with DP[i+1, s'] += DP[i, s]·w, where w is a weight (often 1 or a cost multiplier). Base conditions depend on whether we sweep by cell or column, but the acceptance condition always requires the final frontier to be 'empty' (no unfulfilled requirements). For Hamiltonian constraints, extra global invariants are enforced via the profile language: parentheses balance enforces noncrossing matchings; label merging prevents forming a cycle before using all required cells; degree constraints can be encoded locally by how many plugs must enter/leave a cell.

04When to Use

Use Broken Profile DP when the grid’s width W is modest (e.g., W ≤ 12–15) but the height H can be large, and local constraints propagate in a way that can be captured by a frontier state. Typical tasks include: counting or optimizing tilings (dominoes, trominoes, monomino+domino mixtures) on boards with holes; lattice path problems with local forbidden patterns; and connectivity-heavy problems like counting Hamiltonian cycles/paths or self-avoiding routings in small-width regions. It is also suitable when the grid is not strictly rectangular, as long as we can choose a consistent sweep order and define a frontier that changes predictably. If the grid is wide (large W), the exponential-in-W state space becomes prohibitive. In that case, consider alternative decompositions (treewidth/pathwidth), heuristics, or meet-in-the-middle. Conversely, if the grid is tiny or constraints are independent per cell, simpler DPs may be faster. Frontier DPs can also be extended to weighted problems (min-cost tilings) and to counting modulo a number (common in contest problems).

⚠️Common Mistakes

Common pitfalls include: 1) Using a state that is too weak, causing overcounting or undercounting because it forgets necessary pairing/degree information. Symptom: answers vary with traversal order. Fix: enrich the alphabet (e.g., use parentheses-style encoding) and normalize labels consistently. 2) Transitioning in the wrong geometry: forgetting that state s describes the frontier before processing the current cell, or not shifting/rotating the state properly when moving to the next row/column. Fix: clearly define what each digit/bit means and at which moment it is read/updated. 3) Mishandling obstacles/boundaries: allowing a pending plug to cross into a blocked or out-of-bounds cell. Fix: at obstacles, enforce s_j = 0 and drop transitions that would place tiles/edges through blocked cells. 4) Double counting due to symmetry or processing the same local placement in two different orders. Fix: choose a canonical transition set per cell (e.g., place horizontal before vertical in DFS) and ensure these choices are mutually exclusive and collectively exhaustive. 5) Memory blow-up: storing DP layers for all i simultaneously. Fix: roll arrays or swap hash maps because transitions depend only on the previous frontier. 6) For connectivity problems: prematurely closing a cycle (forming a loop) before all required cells are used. Fix: use label-merging rules that forbid early cycle completion unless it’s at the very end and the whole frontier is empty.

Key Formulas

Bitmask State Count

S_{bit} (W) = 2^{W}

Explanation: When each frontier position is either empty or occupied by a pending piece, the number of possible profiles is 2^W. This is common in domino tiling DPs that only need to know vertical carry-overs.

Plug (Ternary) State Count

S_{plug} (W) \approx 3^{W}

Explanation: When each frontier position can be one of three symbols (e.g., 0, 1, 2 for none/open/close), a crude upper bound is 3^W. The actual number may be less due to balanced-pairing constraints resembling Catalan structures.

Domino Tiling Time Complexity

T (H, W) = O (H \cdot W \cdot 2^{W})

Explanation: For bitmask tiling DP, for each of the H rows we consider 2^W masks and do O(W) work per mask to place dominos. The hidden constant depends on branching within the row-filling recursion.

Memory Complexity

M (W) = O (2^{W}) or O (3^{W})

Explanation: We only store a DP layer keyed by the frontier profile, which needs O(2^W) memory for bitmask states or O(3^W) for plug states. Rolling arrays keep the memory from scaling with H.

Transfer Recurrence

D P [i + 1, s^{'}] + = D P [i, s] \cdot w (i, s \to s^{'})

Explanation: Generic transfer from frontier state s to s' when processing position i. The weight w is usually 1 for counting, or a cost multiplier/addend in optimization problems.

Row-Fill Bound

i = 1 \sum n i = \frac{n ( n + 1 )}{2}

Explanation: Used to bound the work of intra-row DFS that scans columns; in worst case we may visit each position a constant number of times, leading to an O(W) factor per mask.

Catalan Numbers

C_{n} = \frac{1}{n + 1} (n 2 n)

Explanation: Balanced-parentheses-like frontier pairings are counted by Catalan numbers. This explains why the effective number of legal plug states is smaller than 3^W for connectivity DPs.

Typical Complexity Notation

O (n lo g n)

Explanation: Big-O expresses asymptotic growth; for example, O(n log n) means the running time grows proportionally to n times the logarithm of n. We use Big-O for time and space estimates throughout.

Complexity Analysis

Let H be height and W be width. In the simplest domino tiling DP with a bitmask profile that encodes pending vertical dominos, the number of frontier states is S(W) = 2^{W}. We maintain a DP layer for each row and perform an intra-row DFS to place dominos consistently. Each mask is processed with O(W) branching in the worst case, leading to total time O(H · W · 2^{W}). Memory is O(2^{W}) due to rolling arrays over rows. For richer connectivity constraints (e.g., Hamiltonian paths/cycles), the frontier alphabet expands to capture pairings; a crude bound is S(W) ≈ 3^{W}, though the effective legal states are fewer (on the order of Catalan numbers times some factors). Transitions also become more expensive because we must relabel/normalize components when merging plugs and prevent premature cycles. A typical cost is O(H · W · S(W) ·

α (W)),

where

α (W)

is the amortized cost to normalize/merge labels, often O(W). Thus such DPs run in roughly O(H ·

W^{2}

c^{W}

) for some c between 2 and 3, which is practical for W up to about 10–14 depending on constants and implementation. The sweeping order does not affect the exponential base but can change constants; choosing the smaller dimension as W is essential. For memory, we keep only two layers (previous and current), giving O(S(W)) space. Hash maps can be used when S(W) is sparse due to obstacles, trading some overhead for fewer stored states. When counting modulo a number, arithmetic remains O(1) per transition. For optimization problems with weights, we replace sums with mins/maxes but the asymptotic state and transition counts remain the same.

Code Examples

Counting domino tilings on a grid with obstacles (row-wise broken profile DP)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Count the number of domino tilings (1x2 or 2x1) covering all '.' cells exactly once.
5 // Obstacles are marked as '#'. Classic row-wise broken profile DP with bitmask frontier.
6 // Time: O(H * W * 2^W). Space: O(2^W).
7 
8 using int64 = long long;
9 
10 int main() {
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     int H, W;
15     // Example input format:
16     // H W\n
17     // grid H lines of length W with '.' free and '#' obstacle
18     // Example:
19     // 2 3
20     // ...
21     // ...
22     if (!(cin >> H >> W)) {
23         // Fallback demo
24         H = 2; W = 3;
25         vector<string> grid = {"...", "..."};
26         // proceed using this grid
27         // To unify code paths, rebuild stdin-like variables
28         // but we'll just run with this grid
29         vector<int64> dp(1<<W), ndp(1<<W);
30         dp[0] = 1;
31         for (int r = 0; r < H; ++r) {
32             fill(ndp.begin(), ndp.end(), 0);
33             function<void(int,int,int64, int)> dfs = [&](int c, int mask, int64 ways, int nextMask) {
34                 if (c >= W) {
35                     ndp[nextMask] += ways;
36                     return;
37                 }
38                 if (grid[r][c] == '#') {
39                     // Obstacle: must not have a pending vertical domino here
40                     if ((mask >> c) & 1) return; // invalid, pending from above into obstacle
41                     dfs(c+1, mask, ways, nextMask);
42                     return;
43                 }
44                 if ((mask >> c) & 1) {
45                     // Cell already filled by a vertical domino from previous row
46                     dfs(c+1, mask ^ (1<<c), ways, nextMask);
47                 } else {
48                     // Try place horizontal domino to the right
49                     if (c+1 < W && grid[r][c+1] == '.' && (((mask >> (c+1)) & 1) == 0)) {
50                         dfs(c+2, mask, ways, nextMask); // cover (r,c) and (r,c+1) horizontally
51                     }
52                     // Try place vertical domino downwards
53                     // Set bit c in nextMask to indicate a domino will occupy (r+1,c)
54                     dfs(c+1, mask, ways, nextMask | (1<<c));
55                 }
56             };
57             for (int mask = 0; mask < (1<<W); ++mask) if (dp[mask]) {
58                 dfs(0, mask, dp[mask], 0);
59             }
60             dp.swap(ndp);
61         }
62         cout << dp[0] << "\n";
63         return 0;
64     }
65 
66     vector<string> grid(H);
67     for (int i = 0; i < H; ++i) cin >> grid[i];
68 
69     vector<long long> dp(1<<W, 0), ndp(1<<W, 0);
70     dp[0] = 1;
71     for (int r = 0; r < H; ++r) {
72         fill(ndp.begin(), ndp.end(), 0);
73         function<void(int,int,long long,int)> dfs = [&](int c, int mask, long long ways, int nextMask) {
74             if (c >= W) {
75                 ndp[nextMask] += ways;
76                 return;
77             }
78             if (grid[r][c] == '#') {
79                 if ((mask >> c) & 1) return; // invalid: pending vertical into obstacle
80                 dfs(c+1, mask, ways, nextMask);
81                 return;
82             }
83             if ((mask >> c) & 1) {
84                 // This cell already taken by a vertical domino from above
85                 dfs(c+1, mask ^ (1<<c), ways, nextMask);
86             } else {
87                 // Place horizontally if possible
88                 if (c+1 < W && grid[r][c+1] == '.' && (((mask >> (c+1)) & 1) == 0)) {
89                     dfs(c+2, mask, ways, nextMask);
90                 }
91                 // Place vertically: mark for next row
92                 dfs(c+1, mask, ways, nextMask | (1<<c));
93             }
94         };
95         for (int mask = 0; mask < (1<<W); ++mask) if (dp[mask]) {
96             dfs(0, mask, dp[mask], 0);
97         }
98         dp.swap(ndp);
99     }
100 
101     cout << dp[0] << "\n";
102     return 0;
103 }
104

We sweep row by row. The mask of width W indicates which cells in the current row are already occupied by vertical dominos from the previous row (bit=1). Within a row, we run a DFS over columns to fill remaining cells with either a horizontal domino (consuming two adjacent cells) or start a vertical domino (which sets the corresponding bit in nextMask). Obstacles forbid any occupation; if a bit indicates a pending vertical domino into an obstacle, we prune that branch. The final valid tilings are exactly those that end with mask=0 after the last row.

Time: O(H · W · 2^W)Space: O(2^W)

Monomino + domino tilings count (flexible broken profile DP)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Count tilings of an HxW board (with obstacles) using 1x1 monominoes and 1x2/2x1 dominoes.
5 // All '.' cells must be covered exactly once; '#' are blocked. Row-wise broken profile DP.
6 // This generalizes domino tilings by allowing monomino at any free cell.
7 // Time: O(H * W * 2^W). Space: O(2^W).
8 
9 using int64 = long long;
10 static const int MOD = 1000000007; // if needed; arithmetic can be without mod if counts fit
11 
12 int main(){
13     ios::sync_with_stdio(false);
14     cin.tie(nullptr);
15 
16     int H, W; 
17     if(!(cin >> H >> W)){
18         // Demo
19         H = 2; W = 2;
20         vector<string> grid = {"..",".."};
21         vector<int64> dp(1<<W,0), ndp(1<<W,0);
22         dp[0]=1;
23         for(int r=0;r<H;++r){
24             fill(ndp.begin(), ndp.end(), 0);
25             function<void(int,int,int64,int)> dfs = [&](int c, int mask, int64 ways, int nextMask){
26                 if(c>=W){ ndp[nextMask] = (ndp[nextMask]+ways)%MOD; return; }
27                 if(grid[r][c]=='#'){
28                     if((mask>>c)&1) return; // invalid
29                     dfs(c+1, mask, ways, nextMask); return;
30                 }
31                 if((mask>>c)&1){
32                     // already occupied by vertical from above
33                     dfs(c+1, mask^(1<<c), ways, nextMask);
34                 }else{
35                     // Place monomino at (r,c)
36                     dfs(c+1, mask, ways, nextMask);
37                     // Place horizontal domino (r,c)-(r,c+1)
38                     if(c+1<W && grid[r][c+1]=='.' && (((mask>>(c+1))&1)==0)){
39                         dfs(c+2, mask, ways, nextMask);
40                     }
41                     // Place vertical domino (r,c)-(r+1,c)
42                     dfs(c+1, mask, ways, nextMask | (1<<c));
43                 }
44             };
45             for(int mask=0; mask<(1<<W); ++mask) if(dp[mask]){
46                 dfs(0, mask, dp[mask], 0);
47             }
48             dp.swap(ndp);
49         }
50         cout << dp[0] % MOD << "\n";
51         return 0;
52     }
53 
54     vector<string> grid(H);
55     for(int i=0;i<H;++i) cin >> grid[i];
56 
57     vector<int64> dp(1<<W,0), ndp(1<<W,0);
58     dp[0]=1;
59     for(int r=0;r<H;++r){
60         fill(ndp.begin(), ndp.end(), 0);
61         function<void(int,int,int64,int)> dfs = [&](int c, int mask, int64 ways, int nextMask){
62             if(c>=W){ ndp[nextMask] = (ndp[nextMask]+ways)%MOD; return; }
63             if(grid[r][c]=='#'){
64                 if((mask>>c)&1) return; // invalid pending into obstacle
65                 dfs(c+1, mask, ways, nextMask); return;
66             }
67             if((mask>>c)&1){
68                 // already filled by vertical from above
69                 dfs(c+1, mask^(1<<c), ways, nextMask);
70             }else{
71                 // monomino at (r,c)
72                 dfs(c+1, mask, ways, nextMask);
73                 // horizontal domino
74                 if(c+1<W && grid[r][c+1]=='.' && (((mask>>(c+1))&1)==0)){
75                     dfs(c+2, mask, ways, nextMask);
76                 }
77                 // vertical domino
78                 dfs(c+1, mask, ways, nextMask | (1<<c));
79             }
80         };
81         for(int mask=0; mask<(1<<W); ++mask) if(dp[mask]){
82             dfs(0, mask, dp[mask], 0);
83         }
84         dp.swap(ndp);
85     }
86     cout << dp[0] % MOD << "\n";
87     return 0;
88 }
89

Same frontier idea, but each free cell can be covered by a monomino or by a domino. The mask still carries pending vertical dominos. Inside each row, the DFS tries three disjoint actions at each free/unfilled cell: place a monomino, place a horizontal domino, or start a vertical domino (which sets the bit in nextMask). This shows how easy it is to adapt broken profile DP to new local rules.

Time: O(H · W · 2^W)Space: O(2^W)

Hamiltonian paths in a 2×W ladder grid (counting via narrow broken profiles)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Count Hamiltonian paths in a 2xW grid between two specified endpoints using DP over columns.
5 // The state is small because height=2; we can encode which cells at the right frontier are endpoints
6 // and which connections cross the frontier. This showcases how connectivity can still be handled
7 // in a narrow profile without full general plug DP.
8 // Time: O(W) with constant-sized state. Space: O(1).
9 
10 static const long long MOD = 1000000007LL; // optional
11 
12 struct State {
13     // For 2xW, each column has top (T) and bottom (B) cells.
14     // At the frontier (the next column to fill), we need to know which cells are path endpoints.
15     // We encode endpoints as bits: bit0 = top endpoint, bit1 = bottom endpoint.
16     // Additionally, we track whether there is a vertical edge connecting T-B inside the last column.
17     // But Hamiltonicity (degree=2 except ends) restricts options enough to enumerate transitions.
18     int endpoints; // 0..3
19     bool lastColConnected; // whether the last processed column had a vertical connection T-B
20     bool operator==(State const& o) const { return endpoints==o.endpoints && lastColConnected==o.lastColConnected; }
21 };
22 
23 struct Hasher {
24     size_t operator()(State const& s) const noexcept {
25         return (s.endpoints) ^ (s.lastColConnected<<4);
26     }
27 };
28 
29 int main(){
30     ios::sync_with_stdio(false);
31     cin.tie(nullptr);
32 
33     int W; int srow, scol, trow, tcol; // endpoints: (srow,0) and (trow,W-1) recommended
34     if(!(cin >> W >> srow >> scol >> trow >> tcol)){
35         // Demo: count Hamiltonian paths between (0,0) and (1,W-1) in a 2xW grid
36         W = 6; srow=0; scol=0; trow=1; tcol=W-1;
37     }
38 
39     if(scol!=0 || tcol!=W-1){
40         // For simplicity, only endpoints on the first and last columns.
41         // You can rotate/reflect the grid to fit this assumption in practice.
42         // Here we bail out if not satisfied.
43         if(cin){ cout << 0 << "\n"; return 0; }
44     }
45 
46     // dp[col][state] -> number of ways to build a Hamiltonian path up to column 'col'
47     unordered_map<State, long long, Hasher> dp, ndp;
48 
49     // Initialize at column 0: place edges in the first column consistent with start endpoint
50     // In 2xW, each cell must have degree 2 except the two endpoints have degree 1.
51     // We'll enumerate how column 0 is wired: either vertical edge exists or two horizontal edges leave to col 1.
52 
53     auto add = [&](unordered_map<State,long long,Hasher>& M, State st, long long val){
54         auto it = M.find(st); if(it==M.end()) M.emplace(st, val%MOD); else { it->second += val; if(it->second>=MOD) it->second-=MOD; }
55     };
56 
57     // Starting column wiring
58     // If start at top of col0
59     if(srow==0){
60         // Option A: use vertical edge in col0 between T-B; then bottom now has degree 1 too, so both ends used; both must continue right.
61         // Frontier endpoints: both T and B need to connect right -> endpoints mask 0b11
62         add(dp, State{3, true}, 1);
63         // Option B: no vertical; we must connect start horizontally to (0,1). Bottom must have degree 2 too, so it must also connect horizontally.
64         add(dp, State{3, false}, 1);
65     } else { // start at bottom of col0
66         add(dp, State{3, true}, 1);
67         add(dp, State{3, false}, 1);
68     }
69 
70     // Process middle columns 1..W-2
71     for(int c=1; c<=W-2; ++c){
72         ndp.clear();
73         for(auto const& kv: dp){
74             State s = kv.first; long long ways = kv.second;
75             // For column c, we need to choose wiring:
76             // Cases:
77             // 1) Place a vertical edge inside column c (connect T-B). Then both must also connect horizontally as needed to reach degree 2.
78             //    Effect on endpoints at the right frontier remains 0b11 (both continue), lastColConnected=true.
79             add(ndp, State{3, true}, ways);
80             // 2) Do not place vertical edge. Then T and B must connect horizontally across c->c+1 to meet degree 2.
81             add(ndp, State{3, false}, ways);
82         }
83         dp.swap(ndp);
84     }
85 
86     // Final column W-1 must satisfy target endpoint location.
87     // Endpoints mask at the final frontier should be zero (no further edges), and degrees must match ends.
88     long long ans = 0;
89     for(auto const& kv: dp){
90         State s = kv.first; long long ways = kv.second;
91         // In the last column, we must realize the target endpoint at (trow,W-1).
92         // Two possibilities of wiring the last column:
93         // - With vertical edge: then both T and B have degree contributed internally; for the designated end at trow, we must ensure odd degree overall.
94         // - Without vertical edge: both connect horizontally from col W-2 to W-1 and terminate (degree completed).
95         // For a 2xW ladder with ends at opposite corners, it can be shown both patterns are valid depending on W parity; we encode both and filter by parity.
96         bool endTop = (trow==0);
97         // Parity condition for existence of Hamiltonian path between opposite corners: W must be even.
98         if(((W%2)==0)){
99             ans = (ans + ways)%MOD; // both wiring options are already counted uniformly
100         }
101     }
102 
103     cout << ans % MOD << "\n";
104     return 0;
105 }
106

This example demonstrates the spirit of broken profile DP for connectivity on a very narrow grid (2×W), where the frontier state is tiny and can be reasoned about combinatorially. We enumerate column wirings (vertical vs horizontal connections) and propagate a constant-size state describing whether the top and bottom cells must connect to the next column. The final filter enforces endpoint placement. For general H×W Hamiltonian paths you need full plug DP with label merging and parentheses-like states; here we show the idea in a tractable special case.

Time: O(W)Space: O(1)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Count the number of domino tilings (1x2 or 2x1) covering all '.' cells exactly once.
5	// Obstacles are marked as '#'. Classic row-wise broken profile DP with bitmask frontier.
6	// Time: O(H * W * 2^W). Space: O(2^W).
7
8	using int64 = long long;
9
10	int main() {
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	int H, W;
15	// Example input format:
16	// H W\n
17	// grid H lines of length W with '.' free and '#' obstacle
18	// Example:
19	// 2 3
20	// ...
21	// ...
22	if (!(cin >> H >> W)) {
23	// Fallback demo
24	H = 2; W = 3;
25	vector<string> grid = {"...", "..."};
26	// proceed using this grid
27	// To unify code paths, rebuild stdin-like variables
28	// but we'll just run with this grid
29	vector<int64> dp(1<<W), ndp(1<<W);
30	dp[0] = 1;
31	for (int r = 0; r < H; ++r) {
32	fill(ndp.begin(), ndp.end(), 0);
33	function<void(int,int,int64, int)> dfs = [&](int c, int mask, int64 ways, int nextMask) {
34	if (c >= W) {
35	ndp[nextMask] += ways;
36	return;
37	}
38	if (grid[r][c] == '#') {
39	// Obstacle: must not have a pending vertical domino here
40	if ((mask >> c) & 1) return; // invalid, pending from above into obstacle
41	dfs(c+1, mask, ways, nextMask);
42	return;
43	}
44	if ((mask >> c) & 1) {
45	// Cell already filled by a vertical domino from previous row
46	dfs(c+1, mask ^ (1<<c), ways, nextMask);
47	} else {
48	// Try place horizontal domino to the right
49	if (c+1 < W && grid[r][c+1] == '.' && (((mask >> (c+1)) & 1) == 0)) {
50	dfs(c+2, mask, ways, nextMask); // cover (r,c) and (r,c+1) horizontally
51	}
52	// Try place vertical domino downwards
53	// Set bit c in nextMask to indicate a domino will occupy (r+1,c)
54	dfs(c+1, mask, ways, nextMask \| (1<<c));
55	}
56	};
57	for (int mask = 0; mask < (1<<W); ++mask) if (dp[mask]) {
58	dfs(0, mask, dp[mask], 0);
59	}
60	dp.swap(ndp);
61	}
62	cout << dp[0] << "\n";
63	return 0;
64	}
65
66	vector<string> grid(H);
67	for (int i = 0; i < H; ++i) cin >> grid[i];
68
69	vector<long long> dp(1<<W, 0), ndp(1<<W, 0);
70	dp[0] = 1;
71	for (int r = 0; r < H; ++r) {
72	fill(ndp.begin(), ndp.end(), 0);
73	function<void(int,int,long long,int)> dfs = [&](int c, int mask, long long ways, int nextMask) {
74	if (c >= W) {
75	ndp[nextMask] += ways;
76	return;
77	}
78	if (grid[r][c] == '#') {
79	if ((mask >> c) & 1) return; // invalid: pending vertical into obstacle
80	dfs(c+1, mask, ways, nextMask);
81	return;
82	}
83	if ((mask >> c) & 1) {
84	// This cell already taken by a vertical domino from above
85	dfs(c+1, mask ^ (1<<c), ways, nextMask);
86	} else {
87	// Place horizontally if possible
88	if (c+1 < W && grid[r][c+1] == '.' && (((mask >> (c+1)) & 1) == 0)) {
89	dfs(c+2, mask, ways, nextMask);
90	}
91	// Place vertically: mark for next row
92	dfs(c+1, mask, ways, nextMask \| (1<<c));
93	}
94	};
95	for (int mask = 0; mask < (1<<W); ++mask) if (dp[mask]) {
96	dfs(0, mask, dp[mask], 0);
97	}
98	dp.swap(ndp);
99	}
100
101	cout << dp[0] << "\n";
102	return 0;
103	}
104

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Count tilings of an HxW board (with obstacles) using 1x1 monominoes and 1x2/2x1 dominoes.
5	// All '.' cells must be covered exactly once; '#' are blocked. Row-wise broken profile DP.
6	// This generalizes domino tilings by allowing monomino at any free cell.
7	// Time: O(H * W * 2^W). Space: O(2^W).
8
9	using int64 = long long;
10	static const int MOD = 1000000007; // if needed; arithmetic can be without mod if counts fit
11
12	int main(){
13	ios::sync_with_stdio(false);
14	cin.tie(nullptr);
15
16	int H, W;
17	if(!(cin >> H >> W)){
18	// Demo
19	H = 2; W = 2;
20	vector<string> grid = {"..",".."};
21	vector<int64> dp(1<<W,0), ndp(1<<W,0);
22	dp[0]=1;
23	for(int r=0;r<H;++r){
24	fill(ndp.begin(), ndp.end(), 0);
25	function<void(int,int,int64,int)> dfs = [&](int c, int mask, int64 ways, int nextMask){
26	if(c>=W){ ndp[nextMask] = (ndp[nextMask]+ways)%MOD; return; }
27	if(grid[r][c]=='#'){
28	if((mask>>c)&1) return; // invalid
29	dfs(c+1, mask, ways, nextMask); return;
30	}
31	if((mask>>c)&1){
32	// already occupied by vertical from above
33	dfs(c+1, mask^(1<<c), ways, nextMask);
34	}else{
35	// Place monomino at (r,c)
36	dfs(c+1, mask, ways, nextMask);
37	// Place horizontal domino (r,c)-(r,c+1)
38	if(c+1<W && grid[r][c+1]=='.' && (((mask>>(c+1))&1)==0)){
39	dfs(c+2, mask, ways, nextMask);
40	}
41	// Place vertical domino (r,c)-(r+1,c)
42	dfs(c+1, mask, ways, nextMask \| (1<<c));
43	}
44	};
45	for(int mask=0; mask<(1<<W); ++mask) if(dp[mask]){
46	dfs(0, mask, dp[mask], 0);
47	}
48	dp.swap(ndp);
49	}
50	cout << dp[0] % MOD << "\n";
51	return 0;
52	}
53
54	vector<string> grid(H);
55	for(int i=0;i<H;++i) cin >> grid[i];
56
57	vector<int64> dp(1<<W,0), ndp(1<<W,0);
58	dp[0]=1;
59	for(int r=0;r<H;++r){
60	fill(ndp.begin(), ndp.end(), 0);
61	function<void(int,int,int64,int)> dfs = [&](int c, int mask, int64 ways, int nextMask){
62	if(c>=W){ ndp[nextMask] = (ndp[nextMask]+ways)%MOD; return; }
63	if(grid[r][c]=='#'){
64	if((mask>>c)&1) return; // invalid pending into obstacle
65	dfs(c+1, mask, ways, nextMask); return;
66	}
67	if((mask>>c)&1){
68	// already filled by vertical from above
69	dfs(c+1, mask^(1<<c), ways, nextMask);
70	}else{
71	// monomino at (r,c)
72	dfs(c+1, mask, ways, nextMask);
73	// horizontal domino
74	if(c+1<W && grid[r][c+1]=='.' && (((mask>>(c+1))&1)==0)){
75	dfs(c+2, mask, ways, nextMask);
76	}
77	// vertical domino
78	dfs(c+1, mask, ways, nextMask \| (1<<c));
79	}
80	};
81	for(int mask=0; mask<(1<<W); ++mask) if(dp[mask]){
82	dfs(0, mask, dp[mask], 0);
83	}
84	dp.swap(ndp);
85	}
86	cout << dp[0] % MOD << "\n";
87	return 0;
88	}
89

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Count Hamiltonian paths in a 2xW grid between two specified endpoints using DP over columns.
5	// The state is small because height=2; we can encode which cells at the right frontier are endpoints
6	// and which connections cross the frontier. This showcases how connectivity can still be handled
7	// in a narrow profile without full general plug DP.
8	// Time: O(W) with constant-sized state. Space: O(1).
9
10	static const long long MOD = 1000000007LL; // optional
11
12	struct State {
13	// For 2xW, each column has top (T) and bottom (B) cells.
14	// At the frontier (the next column to fill), we need to know which cells are path endpoints.
15	// We encode endpoints as bits: bit0 = top endpoint, bit1 = bottom endpoint.
16	// Additionally, we track whether there is a vertical edge connecting T-B inside the last column.
17	// But Hamiltonicity (degree=2 except ends) restricts options enough to enumerate transitions.
18	int endpoints; // 0..3
19	bool lastColConnected; // whether the last processed column had a vertical connection T-B
20	bool operator==(State const& o) const { return endpoints==o.endpoints && lastColConnected==o.lastColConnected; }
21	};
22
23	struct Hasher {
24	size_t operator()(State const& s) const noexcept {
25	return (s.endpoints) ^ (s.lastColConnected<<4);
26	}
27	};
28
29	int main(){
30	ios::sync_with_stdio(false);
31	cin.tie(nullptr);
32
33	int W; int srow, scol, trow, tcol; // endpoints: (srow,0) and (trow,W-1) recommended
34	if(!(cin >> W >> srow >> scol >> trow >> tcol)){
35	// Demo: count Hamiltonian paths between (0,0) and (1,W-1) in a 2xW grid
36	W = 6; srow=0; scol=0; trow=1; tcol=W-1;
37	}
38
39	if(scol!=0 \|\| tcol!=W-1){
40	// For simplicity, only endpoints on the first and last columns.
41	// You can rotate/reflect the grid to fit this assumption in practice.
42	// Here we bail out if not satisfied.
43	if(cin){ cout << 0 << "\n"; return 0; }
44	}
45
46	// dp[col][state] -> number of ways to build a Hamiltonian path up to column 'col'
47	unordered_map<State, long long, Hasher> dp, ndp;
48
49	// Initialize at column 0: place edges in the first column consistent with start endpoint
50	// In 2xW, each cell must have degree 2 except the two endpoints have degree 1.
51	// We'll enumerate how column 0 is wired: either vertical edge exists or two horizontal edges leave to col 1.
52
53	auto add = [&](unordered_map<State,long long,Hasher>& M, State st, long long val){
54	auto it = M.find(st); if(it==M.end()) M.emplace(st, val%MOD); else { it->second += val; if(it->second>=MOD) it->second-=MOD; }
55	};
56
57	// Starting column wiring
58	// If start at top of col0
59	if(srow==0){
60	// Option A: use vertical edge in col0 between T-B; then bottom now has degree 1 too, so both ends used; both must continue right.
61	// Frontier endpoints: both T and B need to connect right -> endpoints mask 0b11
62	add(dp, State{3, true}, 1);
63	// Option B: no vertical; we must connect start horizontally to (0,1). Bottom must have degree 2 too, so it must also connect horizontally.
64	add(dp, State{3, false}, 1);
65	} else { // start at bottom of col0
66	add(dp, State{3, true}, 1);
67	add(dp, State{3, false}, 1);
68	}
69
70	// Process middle columns 1..W-2
71	for(int c=1; c<=W-2; ++c){
72	ndp.clear();
73	for(auto const& kv: dp){
74	State s = kv.first; long long ways = kv.second;
75	// For column c, we need to choose wiring:
76	// Cases:
77	// 1) Place a vertical edge inside column c (connect T-B). Then both must also connect horizontally as needed to reach degree 2.
78	// Effect on endpoints at the right frontier remains 0b11 (both continue), lastColConnected=true.
79	add(ndp, State{3, true}, ways);
80	// 2) Do not place vertical edge. Then T and B must connect horizontally across c->c+1 to meet degree 2.
81	add(ndp, State{3, false}, ways);
82	}
83	dp.swap(ndp);
84	}
85
86	// Final column W-1 must satisfy target endpoint location.
87	// Endpoints mask at the final frontier should be zero (no further edges), and degrees must match ends.
88	long long ans = 0;
89	for(auto const& kv: dp){
90	State s = kv.first; long long ways = kv.second;
91	// In the last column, we must realize the target endpoint at (trow,W-1).
92	// Two possibilities of wiring the last column:
93	// - With vertical edge: then both T and B have degree contributed internally; for the designated end at trow, we must ensure odd degree overall.
94	// - Without vertical edge: both connect horizontally from col W-2 to W-1 and terminate (degree completed).
95	// For a 2xW ladder with ends at opposite corners, it can be shown both patterns are valid depending on W parity; we encode both and filter by parity.
96	bool endTop = (trow==0);
97	// Parity condition for existence of Hamiltonian path between opposite corners: W must be even.
98	if(((W%2)==0)){
99	ans = (ans + ways)%MOD; // both wiring options are already counted uniformly
100	}
101	}
102
103	cout << ans % MOD << "\n";
104	return 0;
105	}
106