Problem Link - 3xN Tiling
Problem Statement
There is a floor with dimensions K \times N, where K is 1, 2, or 3. You have an infinite supply of tiles of two types:
- Type 1: 2 \times 2 square tiles
- Type 2: 3 \times 1 tiles.
The 3 \times 1 tiles can be rotated and be used as 1 \times 3 tiles as well.
You need to use these tiles to cover the entire floor, in such a way that every cell of the floor is covered by exactly one tile and all the tiles lie completely within the floor. You have to find the number of different ways to doing so. Since the answer might be large, output it modulo 10^9 + 7.
Approach
The problem can be solved using dynamic programming by defining different states based on the size of the floor. For each floor height K, we precompute how many ways we can cover a floor of length N. For K=1, we only need to consider placing vertical or horizontal tiles. For K=2 and K=3, the combinations become more complex because we can use both types of tiles in multiple orientations. The idea is to iteratively compute the number of ways to cover smaller lengths and build up to larger ones by considering how tiles can fit in different positions. The precomputed values are stored in arrays, allowing efficient lookup during each test case.
Time Complexity
O(N) for precomputing the values, and O(1) per query.
Space Complexity
O(N) for storing the precomputed values.