Problem 490 「ジャンプするカエル」

ある池に n 個の石があり, 1 から n まで番号付けされている. 石は連続して1単位ごと間隔を置いて配置されている.

カエルが1の石に座っている. カエルはそれぞれの石を一度だけ訪れて, n の石で止まりたい. しかし, カエルは一つの石から別の石へは高々3単位離れたところにのみジャンプできる. 言い換えると, i の石からカエルは 1 ≤ jn となるような j の石に到達できるとすると, 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.

1 ≤ nL に対し S(L) = ∑ f(n)3 としよう.
例えば:
S(10) = 18230635
S(20) = 104207881192114219
S(1 000) mod 109 = 225031475
S(1 000 000) mod 109 = 363486179

S(1014) mod 109 を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-11-23 (日) 23:46:03 (947d)