### Please also check out other katas in [Domino Tiling series](https://www.codewars.com/collections/5d19554d13dba80026a74ff5)!

---

# Task

A domino is a rectangular block with `2` units wide and `1` unit high. A domino can be placed on a grid in two ways: horizontal or vertical.

```
## or #
      #
```

You have infinitely many dominoes, and you want to fill a board that is `N` units wide and `3` units high:

```
<---   N   --->
###############
###############
###############
```

The task is to find **the number of ways** you can fill the given grid with dominoes.

# The Twist

But you quickly realize that the answer is zero for any odd `N`, because (obviously) you can't cover odd number of cells with dominoes! So you decide to introduce one **unit block** (1 unit wide and 1 unit high) to cover the final gap when needed (you don't need this block when `N` is even).

The following shows some possible tilings for `N = 5`. Note that, unlike my previous Kata, the numbers do not represent the colors (they are just for convenience). Also note that the unit block (marked as 'X') can be placed **anywhere on the board**, making the answers for odd numbers way higher than even ones.

```
11255   1122X   14456
3X267   33447   13356
34467   55667   22X77
```

Since the answer will be very large, please give your answer **modulo 12345787**.

# Examples

```python
# Even input
three_by_n(2) == 3
three_by_n(4) == 11
three_by_n(10) == 571
three_by_n(20) == 413403

# Odd input (the numbers grow much faster than even inputs)
three_by_n(1) == 2
three_by_n(3) == 18
three_by_n(5) == 106
three_by_n(11) == 11542
three_by_n(21) == 3287999

# You must handle big values
three_by_n(9999) == 6311027
three_by_n(10000) == 12003229
```

# Constraints

`1 <= N <= 10000`

All inputs are valid integers.

Difficulty: interview

Starter code:

def three_by_n(n):
	

Solutions:
def three_by_n(n):
    A = [1, 2] + [0]*(n-1)
    B = [0, 1] + [0]*(n-1)
    C = [1, 0] + [0]*(n-1)
    D = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        A[i] = A[i-2] + 2*B[i-1] + 2*C[i-1] + 2*D[i] + 2*D[i-2]
        B[i] = A[i-1] + B[i-2] + C[i-2] + D[i-1]
        C[i] = C[i-2] + 2*D[i-1]
        D[i] = C[i-1] + D[i-2]
    return A[n] % 12345787

# segment the pics and find the law
def countWays(n): 
    A = [0] * (n + 1) 
    B = [0] * (n + 1) 
    A[0] = 1
    A[1] = 2
    B[0] = 0
    B[1] = 1
    for i in range(2, n + 1): 
        if (i % 2):
            B[i] = (A[i - 1] + B[i - 2]) % 12345787
            A[i] = (A[i - 2] + 2 * B[i] + 2 * B[i - 1]) % 12345787
        else:
            A[i] = (A[i - 2] + 2 * B[i - 1]) % 12345787
            B[i] = (A[i - 1] + A[i - 2] + B[i - 1] + B[i - 2]) % 12345787
    return A[n]
    
def three_by_n(n):
    return countWays(n)

a=[1];b=[0];c=[0];d=[0];e=[0];f=[0]
for _ in range(10000):
    aa=b[-1]+c[-1]+f[-1]
    bb=a[-1]+d[-1]
    cc=a[-1]+e[-1]
    dd=b[-1]
    ee=c[-1]
    ff=a[-1]

    a.append(aa%12345787)
    b.append(bb%12345787)
    c.append(cc%12345787)
    d.append(dd%12345787)
    e.append(ee%12345787)
    f.append(ff%12345787)

def three_by_n(n):
    if n%2==0: return a[n]
    tot=0
    for i in range(n):
        tot += d[i]*a[n-i-1] + a[i]*d[n-i-1] + b[i]*b[n-i-1] + a[i]*a[n-i-1]
        tot %= 12345787
    return (2*tot) % 12345787

MOD = 12345787
FLAG = False
f = []

def prework(MAXN=10000):
    nonlocal FLAG
    nonlocal f
    if FLAG:
        return
    FLAG = True
    f = [[[0, 0] for j in range(8)] for i in range(MAXN + 2)]
    # f[i][j][k], k -> already use hole
    f[0][7][0] = 1
    for i in range(MAXN + 1):
        for j in range(7):
            for k in range(3):
                if ((j >> k) & 1) == 0:
                    f[i][j | (1 << k)][1] += f[i][j][0]
        for j in range(8):
            for k in range(2):
                f[i][j][k] %= MOD
        for k in range(2):
            # f[i][*][k] -> f[i+1][?][k]
            f[i + 1][7][k] += f[i][0][k]
            f[i + 1][1][k] += f[i][0][k]
            f[i + 1][4][k] += f[i][0][k]
            f[i + 1][0][k] += f[i][1][k]
            f[i + 1][6][k] += f[i][1][k]
            f[i + 1][5][k] += f[i][2][k]
            f[i + 1][4][k] += f[i][3][k]
            f[i + 1][3][k] += f[i][4][k]
            f[i + 1][0][k] += f[i][4][k]
            f[i + 1][2][k] += f[i][5][k]
            f[i + 1][1][k] += f[i][6][k]
            f[i + 1][0][k] += f[i][7][k]

def three_by_n(n):
    prework()
    return f[n + 1][0][n % 2] % MOD

"""
def three_by_n_without_hole_missing_top(n):
    # the first column can be _11, _12
    assert n%2 == 1
    if n == 1:
        return 1
    return three_by_n_without_hole_missing_top(n-2) \
        + three_by_n_without_hole(n-1)

def three_by_n_without_hole(n):
    # the first column can be 112, 122, 123
    # the first two cases are the same by symmetry
    assert n%2 == 0
    if n == 0:
        return 1
    return three_by_n_without_hole_missing_top(n-1)*2 \
        + three_by_n_without_hole(n-2)

def three_by_n_with_hole_missing_top(n):
    # the first column can be _X1, _1X, _11, _12
    # the second case is impossible because it would have to look like:
    # _225588...
    # 114477....
    # X336699...
    # the fourth case is divided into two cases,
    # depending on whether the next column is X12 or 312
    assert n%2 == 0
    if n == 0:
        return 0
    return three_by_n_without_hole_missing_top(n-1) \
        + three_by_n_with_hole(n-1) \
        + three_by_n_with_hole_missing_top(n-2) \
        + three_by_n_without_hole(n-2)

def three_by_n_with_hole(n):
    # the first column can be X11, X12, 1X2, 11X, 12X, 112, 122, 123
    # by symmetry:
    # case 4 = case 1
    # case 5 = case 2
    # case 7 = case 6
    # note that case 3 is impossible because it would have to look like:
    # 114477....
    # X225588...
    # 336699....
    assert n%2 == 1
    if n == 1:
        return 2
    return three_by_n_without_hole(n-1)*2            \
        + three_by_n_without_hole_missing_top(n-2)*2 \
        + three_by_n_with_hole_missing_top(n-1)*2    \
        + three_by_n_with_hole(n-2)
"""

# naive algorithm
def mat_mul(A,B):
    n = len(A)
    # the top left entry is A[0][0]*B[0][0] + A[0][1]*B[1][0] + ...
    return [[sum(A[i][k]*B[k][j]%12345787 for k in range(n))%12345787 for j in range(n)] for i in range(n)]

# exponentiation by squaring
def mat_pow(A,k):
    n = len(A)
    res = [[0+(i==j) for j in range(n)] for i in range(n)] # A^0
    while k:
        if k%2 == 1:
            res = mat_mul(res,A)
        A = mat_mul(A,A)
        k //= 2
    return res

# let:
# A = three_by_n_without_hole_missing_top
# B = three_by_n_without_hole
# C = three_by_n_with_hole_missing_top
# D = three_by_n_with_hole
# initial cases:
# A[1] = 1
# B[0] = 1
# C[0] = 0
# D[1] = 2
# recursive formulas:
# A[n] =  A[n-2] +  B[n-1]
# B[n] = 2A[n-1] +  B[n-2]
# C[n] =  A[n-1] +  B[n-2] +  C[n-2] + D[n-1]
# D[n] = 2A[n-2] + 2B[n-1] + 2C[n-1] + D[n-2]
# adjust parity
# A[2k+1] =  A[2(k-1)+1] +  B[2k]
# B[2k]   = 2A[2(k-1)+1] +  B[2(k-1)]
# C[2k]   =  A[2(k-1)+1] +  B[2(k-1)] +  C[2(k-1)] + D[2(k-1)+1]
# D[2k+1] = 2A[2(k-1)+1] + 2B[2k]     + 2C[2k]     + D[2(k-1)+1]
# offset
# A[2k+1] = 3A[2(k-1)+1] +  B[2(k-1)]
# B[2k]   = 2A[2(k-1)+1] +  B[2(k-1)]
# C[2k]   =  A[2(k-1)+1]    B[2(k-1)] +  C[2(k-1)] +  D[2(k-1)+1]
# D[2k+1] = 8A[2(k-1)+1] + 4B[2(k-1)] + 2C[2(k-1)] + 3D[2(k-1)+1]

def three_by_n_without_hole(n):
    res = mat_pow([[3,1],[2,1]],n//2)
    return res[0][0]

def three_by_n_with_hole(n):
    res = mat_pow([[3,1,0,0],[2,1,0,0],[1,1,1,1],[8,4,2,3]],n//2)
    return (res[3][0] + res[3][1] + 2*res[3][3])%12345787

def three_by_n(n):
    if n%2 == 1:
        return three_by_n_with_hole(n)
    return three_by_n_without_hole(n)

memo, N, MOD = [0], 10000, 12345787

def three_by_n(n):
    if len(memo) <= N:
        dp = [[0] * (1<<4) for _ in range(2)]
        crt, nxt = dp[0], dp[1]
        crt[0] = 1
        for x in range(N-1, -1, -1):
            for y in range(3-1, -1, -1):
                for used in range(1 << 4):
                    if (used >> y) & 1:
                        nxt[used] = crt[used & ~(1 << y)]
                    else:
                        res = crt[used | 1 << (y+1)] if y+1 < 3 and not(used >> (y+1) & 1) else 0
                        res += crt[used | (1 << y)] if x+1 < N else 0
                        if (used >> 3):
                            nxt[used] = (nxt[used] + res) % MOD
                        else:
                            nxt[used] = res % MOD
                            nxt[used | 1 << 3] = crt[used & ~(1 << y)]
                crt, nxt = nxt, crt
            memo.append(crt[0] if x % 2 == 0 else crt[1<<3])
    return memo[n]

def countWays(n): 
    A = [0] * (n + 1) 
    B = [0] * (n + 1) 
    A[0] = 1
    A[1] = 2
    B[0] = 0
    B[1] = 1
    for i in range(2, n + 1): 
        if (i % 2):
            B[i] = (A[i - 1] + B[i - 2]) % 12345787
            A[i] = (A[i - 2] + 2 * B[i] + 2 * B[i - 1]) % 12345787
        else:
            A[i] = (A[i - 2] + 2 * B[i - 1]) % 12345787
            B[i] = (A[i - 1] + A[i - 2] + B[i - 1] + B[i - 2]) % 12345787
    return A[n]
    
def three_by_n(n):
    return countWays(n)

cache_f = {}
cache_g = {}

def f(n):
    if n in cache_f:
        return cache_f[n]
    if n == 0: return 1
    if n == 1: return 0
    else:
        def g(n):
            if n in cache_g:
                return cache_g[n]
            if n == 0: 
                cache_g[0] = 0
                return 0
            if n == 1: 
                cache_g[1] = 1
                return 1
            else:
                cache_g[n] = f(n-1)+g(n-2)
                return f(n-1)+g(n-2)
        cache_f[n] = f(n-2)+2*g(n-1)
        return f(n-2)+2*g(n-1) 
   
for i in range(1,11):
    f(998*i)
    
def three_by_n(n):
    if n % 2 == 0: return f(n) % 12345787
    else: 
        res = 0
        for i in range((n-1)//2):
            res += cache_g[n-2*(i+1)]*cache_g[2*i+1]*2
        res += (n+1)*cache_g[n]
        return res % 12345787

LST,M = [0,2,3,18,11],12345787

def gen3N():
    Ae,Be,Ao,Bo,Co = 3,8,4,8,6
    while 1:
        Ae,Be, Ao,Bo,Co = [ v%M for v in (Ae+Be, 2*Ae+3*Be ,
                                          Be+Ao+Bo+Co, Be+2*Ao+3*(Bo+Co), 2*(Ae+Be) ) ]
        yield (n%M for n in (Ao+Bo+Co,Ae+Be))

GEN = gen3N()

def three_by_n(n):
    while len(LST) <= n: LST.extend(next(GEN))
    return LST[n]

def three_by_n(n):
    MOD = 12345787
    f = [[1, 0], [1, 2]]
    g = [[0, 1], [0, 1]]
    
    # Without unit block
    for i in range(2, n + 1):
        f[0].append((2 * g[0][i - 1] + f[0][i - 2]) % MOD)
        g[0].append((f[0][i - 1] + g[0][i - 2]) % MOD)
    
    # With unit block
    for i in range(2, n + 1):
        f[1].append((2 * f[0][i - 1] + 2 * g[0][i - 2] + f[1][i - 2] + 2 * g[1][i - 1]) % MOD)
        g[1].append((f[0][i - 2] + g[0][i - 1] + f[1][i - 1] + g[1][i - 2]) % MOD)
    
    return f[1][n]