Project Euler 405
Project Euler 405
题目
A rectangular tiling
We wish to tile a rectangle whose length is twice its width.
Let \(T(0)\) be the tiling consisting of a single rectangle.
For \(n > 0\), let \(T(n)\) be obtained from \(T(n-1)\) by replacing all tiles in the following manner:
The following animation demonstrates the tilings \(T(n)\) for \(n\) from \(0\) to \(5\):
Let \(f(n)\) be the number of points where four tiles meet in \(T(n)\).
For example, \(f(1) = 0, f(4) = 82\) and \(f(10^9) \bmod 17^7 = 126897180\).
Find \(f(10^k)\) for \(k = 10^{18}\), give your answer modulo \(17^7\).
解决方案
可以发现，铺法\(T(n)\)的另一种导出方式如图所示：
它将\(4\)个相同的\(T(n-1)\)按照如上的方式铺设而成。
考虑用动态规划的方法解决本题。使用一个辅助状态\(g(n)(n\ge 0)\)来表示当前铺法\(T(n)\)较长的边上的顶点个数（不包括角上的那\(2\)个顶点）。那么按照当前铺法，\(T(n)\)较短的边上的点的个数为\(g(n-1)\)。
那么不难写出\(g(n)\)的状态转移方程：
\[g(n)= \left \{\begin{aligned} &0 & & \text{if}\quad n=0 \\ &2 & & \text{else if}\quad n=1 \\ &g(n-1)+2g(n-2)+2& & \text{else} \end{aligned}\right.\]
其中，\(g(n)\)的第三行中的第二项表示\(2\)个\(T(n-1)\)上较短的边的顶点个数，第三项表示新产生的\(2\)个顶点，如图所示青色的两个点。
根据\(g(n)\)，不难写出状态\(f(n)\)的状态转移方程：
\[f(n)= \left \{\begin{aligned} &0 & & \text{if}\quad n\le 1 \\ &4f(n-1)+g(n-1)+2g(n-2)& & \text{else} \end{aligned}\right.\]
显而易见，\(4f(n-1)\)是指\(4\)个\(T(n-1)\)铺法内部的点；\(g(n-1)\)则是中间两个\(T(n-1)\)的长边接触所产生的新点（如上图绿色线所标记，铺法\(T\)是上下左右对称的，因此只要长边上有的点都会被计入\(f(n)\)）；而对于第三项，由下图可以知道，在一侧，矩形是按照\(1,2,1,2,1\dots\)的长度铺放，而另外一侧则是\(2,1,2,1,2,\dots\)因此，在铺法\(T(n)\)下，一条橙色边的短边尽管有\(g(n-2)\)个点，但是仅有\(\dfrac{g(n-2)}{2}\)的点和另外一侧是有相交的。因此根据上图有\(4\)条橙色边，由此得到第三个项\(g(n-2)\)。
由于所求目标值\(f(10^{10^{18}})\)过大，因此考虑求出\(f(n)\)的通项公式。
在Mathematica先使用如下命令求出\(g(n)\)：
1 | RSolve[{g[n] == g[n - 1] + 2*g[n - 2] + 2, g[0] == 0, g[1] == 2}, g[n], n] |
得到\(g(n)\)的通项公式为：
\[g(n)=\dfrac{(-1)^{n+1}+2^{n+2}}{3}-1\]
再度运行如下命令求出\(f(n)\)：
1 | g[n_] := 1/3 (-3 + (-1)^(1 + n) + 2^(2 + n)) |
最终得到：
\[f(n) = \dfrac{(-1)^{n+1} - 5 \cdot 2^{n+2} + 6 \cdot 4^n}{15} + 1\]
使用费马小定理直接优化计算过程即可。
代码
1 | from tools import phi, mod_inverse |