ProjectEuler 400 Fibonacci tree game - 拼圖

400. Fibonacci tree game

http://projecteuler.net/problem=400


費氏樹是一個二元樹，定義為：

‧T(0) 是空的樹。

‧T(1) 是二元樹，有一個節點。

‧T(k) 有一個根節點，底下包含了 T(k-1) 跟 T(k-2)，作為根節點的延伸的枝幹。


在這樣成長下的樹，兩個玩家進行了一個"分別拿走"的遊戲。在玩家的回合中，選擇一個

節點拿走，若節點下有附掛其他延伸的枝幹，則一併帶走。

最後把整株費氏樹拿光的玩家為輸。


底下是幾個先手必勝選擇的例子，從 k=1 到 k=6（詳見附圖網址）。

http://projecteuler.net/project/images/p400_winning.png


使 f(k) 為在 T(k) 中，先手必勝選擇的數量（換句話說，後手無論採取什麼策略皆無法

取勝）。


舉例來說，f(5) = 1，f(10) = 17。


請求出 f(10000)。

給出末 18 位數作為您的答案。

------------------------------------------------------------------------------

遲來的翻譯，50席已經坐滿了。

--