490. Jumping frog http://projecteuler.net/problem=490 池塘中有n个石头，编号从1到n，编号相邻的石头间隔为一单位距离 一只青蛙坐在编号为1的石头上，它想要拜访每个石头恰好一次，最後停在编号n的石头上 然而，他只能从一颗石头跳到另一颗石头假若其间隔的距离最多为3单位远。 换句话说，若青蛙在编号为i的石头上，它仅能抵达编号为j的石头上, 1<=j<=n 且j为集合{i-3, i-2, i-1, i+1, i+2, i+3}中的某一元素 令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)为 1<=n<=L的条件下，所有f(n)^3的总和 一些例子： S(10) = 18230635 S(20) = 104207881192114219 S(1 000) 除 10^9 = 225031475 S(1 000 000) 除 10^9 = 363486179 请求出S(10^14) 除 10^9的余数 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 219.70.183.211 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/puzzle/M.1418311885.A.09C.html