Problem400 フィボナッチ木ゲーム

問題

フィボナッチ木とは以下のように再帰的に定義された二分木のことである
●T(0) はノード(節点)を持たない木(空木)である.
●T(1) はノードを一つだけ持つ二分木である.
●T(K) は T(K-1) と T(K-2) を子ノードとして持つルートノード(最上位にあるノード)からなる.

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

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



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

例として f(5) = 1, f(10) = 17 となる.
f(1万)を求めよ. 末尾18桁を回答として答えよ.

ソース

実行結果

解説