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.