### 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.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Ad-hoc

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


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[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 + 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 mat_mul(A, B):
	n = len(A)
	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)]

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

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]


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]]
	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)
	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]