Project Euler 324
Project Euler 324
题目
Building a tower
Let \(f(n)\) represent the number of ways one can fill a \(3\times3\times n\) tower with blocks of \(2\times1\times1\).
You’re allowed to rotate the blocks in any way you like; however, rotations, reflections etc of the tower itself are counted as distinct.
For example (with \(q = 100000007\)) :
\(\begin{aligned} &f(2) = 229,\\ &f(4) = 117805,\\ &f(10) \bmod q = 96149360,\\ &f(10^3) \bmod q = 24806056,\\ &f(10^6) \bmod q = 30808124.\\ \end{aligned}\)
Find \(f(10^{10000}) \bmod 100000007\).
解决方案
令\(N=10^{10000}\)。
将\(f(2)\)和\(f(4)\)放入OEIS中查找,发现结果为A028452。
找到FORMULA
一栏,发现如下信息:
1 | a(n) = 679a(n-1) -76177a(n-2) +3519127a(n-3) -85911555a(n-4) +1235863045a(n-5) -11123194131a(n-6) +65256474997a(n-7) -257866595482a(n-8) +705239311926a(n-9) -1363115167354a(n-10) +1888426032982a(n-11) -1888426032982a(n-12) +1363115167354a(n-13) -705239311926a(n-14) +257866595482a(n-15) -65256474997a(n-16) +11123194131a(n-17) -1235863045a(n-18) +85911555a(n-19) -3519127a(n-20) +76177a(n-21) -679a(n-22) +a(n-23). |
其中,这里的\(a(n)=f(2n)\)。因为很明显知道,当\(m\)为奇数时,\(f(m)=0\)。
因此此时就变成了求\(a\left(\dfrac{N}{2}\right)\)的值。
注意到\(a\)的递推式有\(M=23\)个项,因此使用矩阵快速幂加速时,所使用的矩阵大小\(M\)。因此,考虑使用第258题中的哈密顿-凯莱定理,将计算递推式的时间复杂度进一步降至\(O(M^2 \log N)\)。
代码
此处使用GMP
库对\(N\)进行处理。
本份代码由第258题的代码修改而来。
1 |
|