Problem 400 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 400 へ行く。

*[[Problem 400:http://projecteuler.net/problem=400]] 「フィボナッチ木ゲーム」 [#g01dd795]

''フィボナッチ木''とは以下のように再帰的に定義された二分木のことである:

-T(0) はノード(節点)を持たない木(空木)である.
-T(1) はノードを一つだけ持つ二分木である.
-T(&tex{k};) は T(&tex{k};-1) と T(&tex{k};-2) を子ノードとして持つルートノード(最上位にあるノード)からなる.

このような木構造上で二人の対局者がゲームをする. それぞれの局面で対局者はあるノードを選択し, そのノードをルートとする部分木全体を削除する.~
木全体のルートノードを強制的に取らされた対局者が敗者となる.

&tex{k};=1 から &tex{k};=6 までの T(&tex{k};) に対し最初の局面で先手必勝となる手は以下のようになる. (訳注:赤いノードで示されている)

#ref(p400_winning.png,center,nolink)

T(&tex{k};) の木構造上でゲームをした時, 最初の局面で先手必勝となる(すなわち, 後手が勝てる戦略がない)手の数を &tex{f(k)}; としよう.

例として &tex{f(5)}; = 1, &tex{f(10)}; = 17 となる.

&tex{f(10000)}; を求めよ. 末尾18桁を回答として答えよ.