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://www.ptt.cc/bbs/puzzle/M.1418311885.A.09C.html