587. Tiling a Board With Dominoes

Count the ways to cover an m by n board completely with 1 by 2 dominoes. A domino may be laid flat or upright, dominoes may not overlap, and no square may be left uncovered.

Print the count modulo 1000000007.

2 by 3 -> 3 2 by 2 -> 2 3 by 3 -> 0 an odd number of squares 8 by 8 -> 12988816

## What is new here

Problem 449 counted tilings of a board two rows tall, where a single linear recurrence does the job. This is the general case, and the reason it needs a mask is that a partial tiling of a wide board has a ragged edge, and the shape of that edge is what the next placement has to respect.

## The state is a BOUNDARY, not a set of items

This is the one problem in the topic where the mask is not "which things have been used". Process the squares in column-major order: (column 0, row 0), (column 0, row 1), and so on. At any moment, the covered squares form a prefix of that order plus a few squares poking ahead, and the bits record exactly those.

dp[p][M] = ways to reach square p with M describing the next m squares: bit k of M is 1 when square p + k is already covered

The mask has m bits because a horizontal domino reaches exactly m squares ahead, into the next column and the same row.

## The transitions

Let r = p mod m and col = p div m. At square p with mask M:

· if bit 0 of M is set, the square is already covered, so move on: `` dp[p+1][M >> 1] += dp[p][M] · otherwise the square must be covered NOW, by one of two placements: upright, needs r + 1 < m and bit 1 of M clear: dp[p+1][(M >> 1) | 1] += dp[p][M] flat, needs col + 1 < n: dp[p+1][(M >> 1) | (1 << (m-1))] += dp[p][M]

The shift by one is the move to the next square; the bit that is set afterwards marks whichever future square the new domino reached.

The answer is dp[m*n][0]: every square processed and nothing poking past the end.

## Why the order is the whole design

Every placement covers the CURRENT square. That is what makes the mask only m bits wide and what makes each square decided exactly once, so no tiling is counted twice.

Choosing a different order, for instance "place dominoes wherever they fit", loses both properties at once and is the usual way this problem goes wrong.

## Boundaries

An odd m * n answers 0, and the recurrence reaches that on its own with no special case: the last square can never be covered.

A board one square wide answers 1 when n is even and 0 when it is odd.

## Cost

Time O(m * n * 2^m). Space O(2^m) with a rolling pair of layers.

At m = 10, n = 200 that is about 2 million steps. Put the SMALLER dimension in m when both are under the limit; here the input fixes which is which.

Constraints - `1 ≤ m ≤ 10` - `1 ≤ n ≤ 200`