# 400 : フィボナッチ木ゲーム

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

* $$T(0)$$はノード（節点）を持たない木(空木)である
* $$T(1)$$はノードを一つだけ持つ二分木である
* $$T(k)$$は$$T(k-1)$$と$$T(k-2)$$を子ノードとして持つ根ノード（最上位にあるノード）からなる。

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

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

![p400\_winning.png](https://projecteuler.net/project/images/p400_winning.png)

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

例として$$f(5) = 1, f(10) = 17$$となる。

$$f(10000)$$を求めよ。末尾18桁を回答として答えよ。
