Solution

Answer: 15836928

Let $T(n)$ denote the number of Hamiltonian tours on a $4\times n$ grid that:

start at the top-left square,
end at the bottom-left square,
move only orthogonally,
visit every square exactly once.

We are given:

$$T(10)=2329.$$

We need:

$$T(10^{12}) \pmod{10^8}.$$

1. Mathematical analysis

The key observation is that a Hamiltonian traversal of a fixed-width strip can be described entirely by how paths “cross” between adjacent columns.

Because the width is only $4$, there are only finitely many interface states.

Using a transfer-matrix/state-machine approach, one can classify all legal local boundary configurations and derive a linear recurrence for $T(n)$.

The resulting recurrence is:

$$\boxed{ T(n)=2T(n-1)+2T(n-2)-2T(n-3)+T(n-4) } \qquad (n\ge5)$$

with initial values

$$T(1)=1,\qquad T(2)=1,\qquad T(3)=4,\qquad T(4)=8.$$

We can verify the first few terms:

$$\begin{aligned} T(5)&=2(8)+2(4)-2(1)+1=23,\ T(6)&=2(23)+2(8)-2(4)+1=55,\ T(7)&=144,\ T(8)&=360,\ T(9)&=921,\ T(10)&=2329. \end{aligned}$$

This matches the value given in the problem statement.

Matrix form

Define the vector

$$V_n= \begin{bmatrix} T(n)\ T(n-1)\ T(n-2)\ T(n-3) \end{bmatrix}.$$

Then

$$V_{n+1} = \begin{bmatrix} 2 & 2 & -2 & 1\ 1 & 0 & 0 & 0\ 0 & 1 & 0 & 0\ 0 & 0 & 1 & 0 \end{bmatrix} V_n.$$

$$V_n=M^{,n-4}V_4.$$

Since $n=10^{12}$, direct iteration is impossible, but fast exponentiation computes $M^{10^{12}-4}$ in $O(\log n)$ matrix multiplications.

All arithmetic is performed modulo $10^8$.

2. Python implementation

MOD = 10**8

def mat_mul(A, B):
    """Multiply two 4x4 matrices modulo MOD."""
    n = len(A)
    m = len(B[0])
    k = len(B)

    C = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            s = 0
            for t in range(k):
                s += A[i][t] * B[t][j]
            C[i][j] = s % MOD

    return C

def mat_pow(M, e):
    """Fast exponentiation of matrix M^e modulo MOD."""
    size = len(M)

    # Identity matrix
    R = [[0] * size for _ in range(size)]
    for i in range(size):
        R[i][i] = 1

    while e > 0:
        if e & 1:
            R = mat_mul(R, M)

        M = mat_mul(M, M)
        e >>= 1

    return R

def solve(n):
    # Initial values:
    # T1 = 1, T2 = 1, T3 = 4, T4 = 8
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n == 3:
        return 4
    if n == 4:
        return 8

    # Transition matrix
    M = [
        [2, 2, -2, 1],
        [1, 0, 0, 0],
        [0, 1, 0, 0],
        [0, 0, 1, 0]
    ]

    # Convert negatives modulo MOD
    for i in range(4):
        for j in range(4):
            M[i][j] %= MOD

    # State vector at n=4:
    # [T4, T3, T2, T1]^T
    V = [
        [8],
        [4],
        [1],
        [1]
    ]

    P = mat_pow(M, n - 4)

    result = mat_mul(P, V)

    return result[0][0] % MOD

print(solve(10))          # 2329
print(solve(10**12))

3. Code walkthrough

Matrix multiplication

def mat_mul(A, B):

Computes matrix multiplication modulo $10^8$.

Fast exponentiation

def mat_pow(M, e):

Uses binary exponentiation:

if exponent bit is set, multiply into result,
square the matrix each step,
divide exponent by 2.

Complexity is only $O(\log n)$.

Transition matrix

M = [
    [2, 2, -2, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0]
]

This encodes

$$T(n)=2T(n-1)+2T(n-2)-2T(n-3)+T(n-4).$$

The lower rows simply shift the state vector.

Initial vector

V = [[8],[4],[1],[1]]

corresponds to

$$[T(4),T(3),T(2),T(1)]^T.$$

Verification

The program gives:

solve(10) = 2329

matching the problem statement exactly.

4. Final verification

The recurrence reproduces all known small values correctly, including the required check: