Project Euler 237

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

Project Euler 237

题目

Tours on a $4 \times n$ playing board

Let $T(n)$ be the number of tours over a $4 \times n$ playing board such that:

  • The tour starts in the top left corner.
  • The tour consists of moves that are up, down, left, or right one square.
  • The tour visits each square exactly once.
  • The tour ends in the bottom left corner.

The diagram shows one tour over a $4 \times 10$ board:

$T(10)$ is $2329$. What is $T(10^{12}) \text{ modulo } 10^8$?

解决方案

两个子问题：

第一个问题：求出关于$4\times n$格子上以$(1,1)$为起点，以$(4,1)$为终点的路径数$T(n)$的关系式。（参考了Thread中的信息。）

使用暴力程序找出前几项后，查找OEIS，发现结果为A181688。在FORMULA一栏中，发现如下信息：

1
a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4), n > 4.

再根据前几项枚举出来的值，不难发现$T$的递推公式为：

第二个问题：优化

上面的递推式需要$O(n)$的时间复杂度才能计算出具体值，因此改用矩阵快速幂，将计算递推式的值的时间复杂度降到$O(\log n)$。将线性递推式写成矩阵相乘的形式：

令矩阵$A$为：

$A=\begin{bmatrix}
2 & 2 & -2 & 1\
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0
\end{bmatrix}$

那么可以将递推式写成矩阵相乘的形式：

通过该递推式可以产生矩阵$A$的幂。而矩阵$A$的幂次方$A^n$也可以在对数时间完成计算。因此能以$O(\log n)$的时间复杂度计算$T(n)$的值。

代码

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


def mul(a: list, b: list):
    return [[sum(a[i][k] * b[k][j] for k in range(len(b))) % mod for j in range(len(b[0]))] for i in range(len(a))]


a = [[1, 1, 4, 8]]
b = [[0, 0, 0, 1], [1, 0, 0, -2], [0, 1, 0, 2], [0, 0, 1, 2]]
N -= 1
while N:
    if N & 1:
        a = mul(a, b)
    b = mul(b, b)
    N >>= 1
ans = a[0][0]
print(ans)