Profile DP and Broken Profile DP

Profile DP compresses a partially built grid into its narrow boundary. For domino tilings, we only need to know which cells in the next row are already occupied by vertical dominoes from the previous row. Processing one cell at a time inside that boundary is often called broken-profile DP. Small width, not merely small total area, is the practical clue.

Prerequisites: Bitmask DP; recursive generation; rolling arrays.

Build the idea

1. Recognize the repeated subproblems

   Placing dominoes in arbitrary board order repeats many partial arrangements that expose the same boundary. A grid of width≤10 has only 2^width row masks, even if height is 100. Complete placement histories below the processed boundary no longer affect the future; only protruding dominoes do. Obstacles or different tile shapes may require modified transition rules or a thicker profile.

2. Define the state

   dp[mask] after a row boundary counts tilings of processed rows whose vertical dominoes occupy mask’s cells in the next row. Each bit names a column. Transition generation receives an incoming occupied mask and builds a next mask. The code rotates the rectangle so width is the smaller dimension; rotation preserves plain domino tiling counts.

3. Derive the transition

   Find the first unprocessed column. If occupied, skip it. Otherwise place a vertical domino, marking that column in next, or place a horizontal domino if its neighboring cell is also free and inside the row. Continue until the row is fully accounted for, then emit next. This first-free-cell rule gives a unique generation path for each local placement, avoiding double-counting from arbitrary tile-placement order.

   $$\mathrm{next}\left[\mathrm{out}\right]+=\mathrm{dp}\left[\mathrm{in}\right]\mathrm{for}\mathrm{each}\mathrm{legal}\mathrm{row}\mathrm{filling}$$

4. Base cases and computation order

   Before any row, dp[0]=1 and other masks zero. Precompute outgoing masks for every incoming mask, then apply those transitions once per row with fresh next counts. At the final boundary, only mask zero is accepted; nonzero masks represent dominoes protruding beyond the board. Modulo 10^9+7 controls counts. A nonzero final partial state is not a complete tiling.

5. Correctness and invariant

   Induct on row boundaries. The incoming mask exactly records prior-row occupancy; generated placements neither overlap those cells nor leave a current-row cell uncovered. Every valid completion has a unique tile covering the first free cell, so recursion enumerates all local options once. Combining disjoint previous tilings with these transitions counts every full tiling once. Requiring final zero closes the boundary.

6. Work the example

   For a 3×2 rectangle, reachable masks are 00 and 11. Starting counts (1,0) become (1,1),(2,1),(3,2) after successive rows. The complete answer is the zero-mask count 3, not total 5, which would include unfinished protrusions. These are the familiar three arrangements of three dominoes in a two-column board.

   processed rows	mask 00	mask 11
   0	1	0
   1	1	1
   2	2	1
   3	3	2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
void fillRow(int col,int width,int occupied,int next,std::vector<int>&output){
    if(col==width){
        output.push_back(next);
        return;
    }
    if(occupied>>col&1){
        fillRow(col+1,width,occupied,next,output);
        return;
    }
    fillRow(col+1,width,occupied,next|(1<<col),
        output); // Vertical domino continues into the next row.
    if(col+1<width&&!(occupied>>(col+1)&1)){
        fillRow(col+2,width,occupied,next,output); // Horizontal domino covers both free cells.
    }
}
int main(){
    int height,width;
    std::cin>>height>>width;
    if(width>height){
        std::swap(width,height);
    }
    int masks=1<<width;
    const long long MOD=1000000007;
    std::vector<std::vector<int>>transitions(masks);
    for(int mask=0;mask<masks;++mask){
        fillRow(0,width,mask,0,transitions[mask]);
    }
    std::vector<long long>dp(masks),next(masks);
    dp[0]=1;
    for(int row=0;row<height;++row){
        std::fill(next.begin(),next.end(),0);
        for(int mask=0;mask<masks;++mask){
            for(int out:transitions[mask]){
                next[out]=(next[out]+dp[mask])%MOD;
            }
        }
        dp.swap(next);
    }
    std::cout<<dp[0]<<'\n'; // Only zero final protrusion is a complete tiling.
}

Complexity analysis

With W=min dimensions, H=max, there are 2^W boundary states. Across all masks, the number of valid incoming/outgoing pairs is≤3^W:each column is incoming, outgoing or horizontally filled. Conservative generation cost O(W·3^W), row propagation O(H·3^W), space O(3^W+2^W) for transitions/rolling counts. Exponential width remains the limitation.

Example input and output

Read positive height width, each≤100 and min(height, width)≤10. Tile the empty rectangle with 1×2/2×1 dominoes. Print complete tiling count modulo 10^9+7.

Input

3 2

Output

3

For a 3×2 rectangle, reachable masks are 00 and 11. Starting counts (1,0) become (1,1),(2,1),(3,2) after successive rows. The complete answer is the zero-mask count 3, not total 5, which would include unfinished protrusions. These are the familiar three arrangements of three dominoes in a two-column board.

Practical applications

Use for narrow tiling, connectivity and placement problems where a small frontier captures future constraints. Connectivity profiles need more than occupancy bits. Broken-profile cell traversal can avoid regenerating equivalent arbitrary placement orders.

Check your understanding

Why is only dp[0] a complete answer after the last row?

Put it into practice

Compare with first-free-cell exhaustive tiling on boards up to 5×5.