449. Tiling a Two-Row Board
Count the ways to tile a 2 by n board completely, using 2 x 1 dominoes in
either orientation and L-shaped trominoes in any of their four rotations. Print the
count MODULO 1000000007.
Tilings are different if any cell is covered by a differently placed piece.
n = 1 -> 1
n = 2 -> 2
n = 3 -> 5
n = 4 -> 11
Problem #234 counts domino-only tilings, which is Fibonacci. Adding the tromino changes the recurrence entirely, and the reason is that a tromino leaves a RAGGED edge: after placing one, the boundary is no longer a clean vertical line, so the state cannot be "columns filled so far" alone.
Working the cases through gives:
f(1) = 1, f(2) = 2, f(3) = 5
f(n) = 2 * f(n-1) + f(n-3)
That recurrence is short and its derivation is not obvious, which makes it exactly
the kind of result worth CHECKING rather than trusting. The expected outputs here
were verified against an exhaustive bitmask tiling of the board for every n up to
12 before being used, and the first attempt at that verification was itself wrong,
because it allowed pieces to extend only rightwards and so missed the rotation that
reaches left.
Reduce modulo the prime at every step. The count passes 10^18 around n = 60.
Constraints - `1 ≤ n ≤ 1000`
Input
One line containing the integer n.
Output
Print the number of tilings modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.