You have a 4 × n board. Count the number of distinct ways to tile it using 2 × 1 dominoes (rotation allowed).

Problem

Given an integer n >= 1, compute the number of different tilings of a 4 × n board using 2 × 1 dominoes. Dominoes may be placed horizontally or vertically; all tiles must fully cover the board without overlap.

Examples

Example 1

1
2
3

Input: n = 1
Output: 1
Explanation: Only a single vertical column of four vertical dominoes fits.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: n = 2
Output: 5
Explanation: There are five tilings of a 4×2 board — all-vertical, and four patterns with two horizontal dominoes occupying one of the two rows (symmetries accounted for). Small enumeration:

1) All vertical dominoes (one per column)
2) Two horizontals covering top two cells and two verticals below
3) Two horizontals covering second row, verticals elsewhere
4) Two horizontals covering third row, verticals elsewhere
5) Two horizontals covering bottom row, verticals elsewhere

(Total = 5)

Example 3

1
2
3

Input: n = 4
Output: 36
Explanation: There are 36 distinct tilings of a 4×4 board with 2×1 dominoes.

Solution

We present a concise derivation of the standard linear recurrence for f(n) (the number of tilings) and two practical algorithms: a linear DP and a fast matrix-exponentiation method for large n.

Method 1 — Recurrence derivation (combinatorial decomposition)

Intuition

Look at how a tiling of the 4 × n board can begin at the leftmost columns. There are a fixed set of local starting patterns (eight canonical types). Group tilings by their starting pattern and relate f(n) to values f(k) for smaller k by removing covered columns; this yields a linear recurrence.

Approach (high level)

  1. Let f(n) be the number of tilings of a 4 × n board. Handle small n by inspection:

    • f(1) = 1, f(2) = 5, f(3) = 11, f(4) = 36.

  2. Enumerate the distinct ways a valid tiling can occupy the leftmost 1–4 columns (these are the eight starting types A..H in the classical derivation).

  3. Count contributions from each type and express f(n) in terms of f(n-1), f(n-2), f(n-3), and f(n-4).

  4. Simplifying the combinatorial bookkeeping gives the recurrence

    f(n) = f(n-1) + 5*f(n-2) + f(n-3) - f(n-4)

    with base values listed above.

This recurrence is classical; a clear derivation follows by grouping types and using inclusion/exclusion on the dependent patterns (see references in source_links).

Code

Method 2 — Dynamic programming (tabulation)

Intuition

Use the recurrence directly. Compute f(1..n) iteratively from the base cases.

Approach

  1. If n <= 4 return precomputed base values.
  2. Allocate an array f of length n+1 and initialize base cases.
  3. For i from 5..n compute f[i] = f[i-1] + 5*f[i-2] + f[i-3] - f[i-4] (apply modulo if required).
  4. Return f[n].

Edge cases: n small (<=4) handled by base values. For very large n use Method 3.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
    long long fillingBlocks(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 5;
        if (n == 3) return 11;
        if (n == 4) return 36;
        const long long MOD = 1000000007LL;
        std::vector<long long> f(n+1);
        f[1]=1; f[2]=5; f[3]=11; f[4]=36;
        for (int i=5;i<=n;++i) {
            f[i] = (f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]) % MOD;
            if (f[i] < 0) f[i] += MOD;
        }
        return f[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

func fillingBlocks(n int) int64 {
        if n <= 0 { return 0 }
        if n == 1 { return 1 }
        if n == 2 { return 5 }
        if n == 3 { return 11 }
        if n == 4 { return 36 }
        const MOD int64 = 1000000007
        f := make([]int64, n+1)
        f[1], f[2], f[3], f[4] = 1, 5, 11, 36
        for i := 5; i <= n; i++ {
                v := f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]
                v %= MOD
                if v < 0 { v += MOD }
                f[i] = v
        }
        return f[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long fillingBlocks(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 5;
        if (n == 3) return 11;
        if (n == 4) return 36;
        final long MOD = 1_000_000_007L;
        long[] f = new long[n+1];
        f[1]=1; f[2]=5; f[3]=11; f[4]=36;
        for (int i = 5; i <= n; ++i) {
            long v = (f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]) % MOD;
            if (v < 0) v += MOD;
            f[i] = v;
        }
        return f[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from typing import List

class Solution:
        def filling_blocks(self, n: int) -> int:
                if n <= 0: return 0
                if n == 1: return 1
                if n == 2: return 5
                if n == 3: return 11
                if n == 4: return 36
                MOD = 10**9+7
                f = [0] * (n+1)
                f[1], f[2], f[3], f[4] = 1, 5, 11, 36
                for i in range(5, n+1):
                        v = f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]
                        v %= MOD
                        f[i] = v
                return f[n]

Complexity

  • ⏰ Time complexity: O(n) — single loop computing f[i] from previous four values.
  • 🧺 Space complexity: O(n) — the DP array; can be reduced to O(1) by keeping only the last four values.

Method 3 — Fast exponentiation via linear recurrence (matrix power)

Intuition

The recurrence is linear with constant coefficients of order 4. We can express the state vector S(i) = [f(i), f(i-1), f(i-2), f(i-3)]^T and a fixed 4×4 transition matrix M such that S(i+1) = M * S(i). Then S(n) = M^{n-4} * S(4) and we can compute M^{n} in O(log n) matrix multiplications.

Approach

  1. Build the 4×4 transition matrix M corresponding to the recurrence f(i) = f(i-1) + 5f(i-2) + f(i-3) - f(i-4).
  2. Use fast exponentiation to compute M^{k} in O(log k) matrix multiplications (each multiplication is O(4^3)=O(1) constant work).
  3. Multiply M^{n-4} by S(4) = [f(4), f(3), f(2), f(1)]^T to get f(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
 public:
    using ll = long long;
    const ll MOD = 1000000007LL;

    vector<vector<ll>> mul(const vector<vector<ll>>& A, const vector<vector<ll>>& B) {
        int m = 4;
        vector<vector<ll>> C(m, vector<ll>(m));
        for (int i = 0; i < m; ++i)
            for (int k = 0; k < m; ++k)
                for (int j = 0; j < m; ++j)
                    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD;
        return C;
    }

    vector<vector<ll>> mpow(vector<vector<ll>> base, long long e) {
        int m = 4;
        vector<vector<ll>> res(m, vector<ll>(m));
        for (int i = 0; i < m; ++i) res[i][i] = 1;
        while (e > 0) {
            if (e & 1) res = mul(res, base);
            base = mul(base, base);
            e >>= 1;
        }
        return res;
    }

    long long fillingBlocksFast(long long n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 5;
        if (n == 3) return 11;
        if (n == 4) return 36;
        vector<vector<ll>> M = {
            {1,5,1,MOD-1},
            {1,0,0,0},
            {0,1,0,0},
            {0,0,1,0}
        };
        auto P = mpow(M, n-4);
        vector<ll> S4 = {36,11,5,1};
        ll ans = 0;
        for (int j = 0; j < 4; ++j) ans = (ans + P[0][j]*S4[j]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from typing import List

class Solution:
        MOD = 10**9+7

        def mat_mul(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
                m = 4
                C = [[0]*m for _ in range(m)]
                for i in range(m):
                        for k in range(m):
                                for j in range(m):
                                        C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % self.MOD
                return C

        def mat_pow(self, base: List[List[int]], e: int) -> List[List[int]]:
                m = 4
                res = [[0]*m for _ in range(m)]
                for i in range(m): res[i][i] = 1
                while e > 0:
                        if e & 1:
                                res = self.mat_mul(res, base)
                        base = self.mat_mul(base, base)
                        e >>= 1
                return res

        def filling_blocks_fast(self, n: int) -> int:
                if n <= 0: return 0
                if n == 1: return 1
                if n == 2: return 5
                if n == 3: return 11
                if n == 4: return 36
                M = [
                        [1,5,1,(self.MOD-1)],
                        [1,0,0,0],
                        [0,1,0,0],
                        [0,0,1,0]
                ]
                P = self.mat_pow(M, n-4)
                S4 = [36,11,5,1]
                ans = 0
                for j in range(4):
                        ans = (ans + P[0][j]*S4[j]) % self.MOD
                return ans

Complexity

  • ⏰ Time complexity: O(log n) for the matrix-exponentiation method (each multiplication is constant-sized 4×4 work, exponentiation takes O(log n) steps).
  • 🧺 Space complexity: O(1) (constant extra space for matrices) beyond input/output.