← 完整题目索引

PROJECT EULER · #0490

跳蛙

Jumping Frog

仅题目 · 待解原题 ↗

池塘里有 n 石头,编号为 1 到 n。连续的石子间隔一单位。

一只青蛙坐在石头 1 上。他希望每块石头都访问一次,并在 n 石头上停下来。然而,他只能从一块石头跳到另一块石头,前提是它们之间的距离最多为 3 单位。换句话说,如果 1≤j≤n 和 j 在集合 {i−3,i−2,i−1,i+1,i+2,i+3} 中,那么从石头 i 开始,他可以到达石头 j。

令 f(n) 为他可以做到这一点的方法数量。例如f(6)=14,如下图:
1→2→3→4→5→6
1→2→3→5→4→6
1→2→4→3→5→6
1→2→4→5→3→6
1→2→5→3→4→6
1→2→5→4→3→6
1→3→2→4→5→6
1→3→2→5→4→6
1→3→4→2→5→6
1→3→5→2→4→6
1→4→2→3→5→6
1→4→2→5→3→6
1→4→3→2→5→6
1→4→5→2→3→6

其他示例有 f(10)=254 和 f(40)=1439682432976。

让 S(L)=∑f(n)3 为 1≤n≤L。
示例:
S(10)=18230635
S(20)=104207881192114219
S(1000)mod109=225031475
S(1000000)mod109=363486179

查找 S(1014)mod109。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。