Problem 400

Fibonacci tree game

A Fibonacci tree is a binary tree recursively defined as:

T(0) is the empty tree.
T(1) is the binary tree with only one node.
T(k) consists of a root node that has T(k-1) and T(k-2) as children.

On such a tree two players play a take-away game. On each turn a player selects a node and removes that node along with the subtree rooted at that node.
The player who is forced to take the root node of the entire tree loses.

Here are the winning moves of the first player on the first turn for T(k) from k=1 to k=6.

Let f(k) be the number of winning moves of the first player (i.e. the moves for which the second player has no winning strategy) on the first turn of the game when this game is played on T(k).

For example, f(5) = 1 and f(10) = 17.

Find f(10000). Give the last 18 digits of your answer.

斐波那契树游戏

斐波那契树是一棵递归定义的二叉树：

T(0)是一棵空树。
T(1)是只有一个结点的二叉树。
T(k)有一个根结点，其左右子树分别为T(k-1)和T(k-2)。

在这棵树上，两个玩家进行一个取结点游戏。每一回合，一名玩家选择一个结点，并取走以这个结点为根结点的子树。
取走整棵树的根结点的玩家将输掉这个游戏。

以下是当k=1~6时，先手玩家面对T(k)第一步所有的必胜走法：

记f(k)是先手玩家面对T(k)时第一步所有的必胜走法数目（所谓必胜走法指保证后手玩家没有必胜策略）。

例如，f(5) = 1以及f(10) = 17。

求f(10000)。给出其最后18位数作为你答案。