Problem 400 の変更点

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

#author("2024-05-19T02:19:59+00:00","","")
*[[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)
#ref("https://projecteuler.net/resources/images/0400_winning.png",center,nolink)

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

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

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

IP:121.80.134.87 TIME:"2024-05-19 (日) 11:19:59" REFERER:"https://odz.sakura.ne.jp/projecteuler/" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/124.0.0.0 Safari/537.36"