DT-Tiling

Frontier states

Suppose every cell strictly to the left of the current column has been filled. Since a horizontal straight tromino has length $3$, tiles already placed can occupy cells only in the current and next columns. Encode these four cells as a bitmask: bits $0,1$ represent the top and bottom cells of the current column, and bits $2,3$ represent those of the next column.

Place a tile covering the first empty cell of the current column. Once that column is full, shift the mask right by two bits. Always choosing the first empty cell avoids counting the same tiling in different placement orders. Start at mask $0$ and accept only mask $0$ after processing $N$ columns.

The reachable masks are $0,1,2,3,5,7,10,11,15$. Vertical reflection gives equal counts for symmetric masks. After $n$ columns, define six quantities:

• $f_n$: the count for mask $0$.
• $u_n$: the count for mask $1$, equal to that for mask .

Each quantity stores the count of one mask, not the sum of a symmetric pair. Enumerating placements covering the first empty cell gives the following transitions.

$$\begin{array}{rl}{\displaystyle f_{n+1}}& {\displaystyle =f_n+v_n,}\\ {\displaystyle u_{n+1}}& {\displaystyle =f_n+u_n+x_n,}\\ {\displaystyle v_{n+1}}& {\displaystyle =f_n+2u_n+2w_n+y_n,}\\ {\displaystyle w_{n+1}}& {\displaystyle =u_n,}\\ {\displaystyle x_{n+1}}& {\displaystyle =f_n+w_n,}\\ \end{array}$$ $$(f_0,u_0,v_0,w_0,x_0,y_0)=(1,0,0,0,0,0).$$

Linear DP and matrix exponentiation

Evaluating the transitions $N$ times takes $O(N)$ time and $O(1)$ space, sufficient for subtask 2. For the full constraints, write the six quantities as a column vector with $s_{n+1}=Ms_n$, where

$$M=(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 1& 2& 0& 2& 0& 1\\ 0& 1& 0& 0& 0& 0\\ 1& 0& 0& \end{array}$$

Binary exponentiation computes $M^N$ in $O(6^3\log N)$ time and $O(6^2)$ space. Perform all arithmetic modulo .

Recurrence used in the supplied code

The transition matrix satisfies

$$M^6=2M^5+3M^3+2M^2+M-I.$$

Hence, for $n\geq6$,

$$f_n=2f_{n-1}+3f_{n-3}+2f_{n-4}+f_{n-5}-f_{n-6},$$

with

$$(f_0,f_1,f_2,f_3,f_4,f_5)=(1,1,2,6,17,43).$$

The supplied linear solution evaluates this recurrence directly. The main solution exponentiates its $6\times6$ companion matrix on the state $(f_n,f_{n-1},\cdots,f_{n-5})$. Represent the coefficient by the modulus minus one, and store the exponent in a 64-bit integer.

Small-case search

For subtask 1, represent all $2N$ board cells by a bitmask and try every tile covering the first empty cell. Memoize each occupied-cell mask. Filling cells from left to right leaves only a constant number of frontier states per column, since protrusions span at most two future columns. Scanning for the first empty cell gives $O(N^2)$ time and $O(N)$ stored states. The independent naive implementation uses at most 40 bits for the whole board.

Both straight and L-shaped trominoes are required. A vertical straight tromino does not fit in a height-two board. The empty-board value $f_0=1$ is an internal base case; input never has $N=0$.

Reduce after each multiply-add. Each intermediate is at most $(10^9+6)^2+(10^9+6)<1.01\cdot10^{18}$, so signed 64-bit arithmetic suffices.

Solution written by GPT