Problem statement

https://binarysearch.com/problems/Dominos/

Solution 1

We can find recurrent here and use dp.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, n):
        if n % 2 == 1: return 0
        x, y = 1, 0
        for i in range(2, n+1, 2):
            x, y = 3*x + y, 2*x + y

        return x % (10 ** 9 + 7)

Solution 2

Here is also universal solution for n x m grid, using bit-dp technique and broken profile.

Complexity

It is O(2^m * m * n) for time and space.

Code

class Solution:
    def solve(self, n):
        m, M = 3, 10**9 + 7
        @lru_cache(None)
        def dp(index, mask):
            ax, mask2 = 1 << (m-1), mask >> 1
            if index == -1: return  int(mask == (1<<m) - 1)
            R, C, ans = index//m, index%m, 0

            if mask % 2 == 0: 
                ans = dp(index-1, mask2 + ax)
            else:
                if R <= n - 1: ans += dp(index-1, mask2)
                if C > 0 and mask % 4 == 3: ans += dp(index-1, mask2 + ax - 1)
            return ans % M

        return dp(m*n - 1, (1<<m) - 1)

Remark

There is also matrix power solution with complexity O(3^3 * log n).