[中譯] ProjectEuler 490 Jumping frog

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者utomaya (烏托馬雅)時間11年前 (2014/12/11 23:31)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

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