Detailed mathematical approach

Problem Summary

Let \(T_k\) be the Fibonacci tree of order \(k\): \(T_1\) is a single vertex, \(T_2\) is a single edge, and for \(n \ge 3\) the root of \(T_n\) has two child branches that are copies of \(T_{n-1}\) and \(T_{n-2}\). A legal move cuts one edge and deletes the detached subtree. The quantity \(f(k)\) computed by the implementation is the number of first moves on \(T_k\) that leave a position with Grundy value \(0\), and the final answer is required modulo \(10^{18}\).

Mathematical Approach

Step 1: Grundy Value of One Branch

For any rooted tree \(X\), let \(G(X)\) denote its Sprague-Grundy value. The game on the whole tree splits into independent games on the branches attached to the root, so the total Grundy value is the XOR of the branch contributions.

Now consider a single branch consisting of one edge from the parent to a child subtree \(Y\). If \(G(Y)=g\), then cutting the top edge removes the whole branch and produces contribution \(0\). Any move inside \(Y\) replaces \(Y\) by one of its option values \(u\), so the branch contribution becomes \(1+u\).

Because a subtree of Grundy value \(g\) has options that realize every value \(0,1,\dots,g-1\) and avoid \(g\), the branch has options

$0,1,2,\dots,g,$

but not \(g+1\). Therefore the branch itself has Grundy value

$B(Y)=1+G(Y).$

Step 2: Fibonacci Recurrence for the Full Tree

Write \(G_n=G(T_n)\). The base trees are immediate:

$G_1=0,\qquad G_2=1.$

For \(n \ge 3\), the root of \(T_n\) has branches \(T_{n-1}\) and \(T_{n-2}\). Using the branch rule above and the XOR rule for disjoint impartial subgames, we obtain

$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$

The first few values are

$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$

This precomputation is exactly what the implementation performs before counting any moves.

Step 3: Count Cuts That Produce a Target Grundy Value

To count winning moves, define \(C_n(t)\) as the number of ways to make exactly one cut in a branch that is a copy of \(T_n\) so that the surviving rooted branch has Grundy value \(t\). For the recursion it is convenient to extend the state space by the bookkeeping value \(t=-1\): this does not represent a real Grundy number, but the case where the attachment edge itself is cut and the whole branch disappears.

Suppose we are at \(T_n\) with \(n \ge 3\). A cut occurs either inside the \(T_{n-2}\) branch or inside the \(T_{n-1}\) branch.

If the cut is made in the \(T_{n-2}\) branch and that branch ends in bookkeeping state \(u\), then the unchanged \(T_{n-1}\) branch still contributes \(1+G_{n-1}\), while the modified branch contributes \(1+u\). Hence the total Grundy value becomes

$t=(1+G_{n-1})\oplus(1+u).$

Solving for \(u\) gives

$u=((1+G_{n-1})\oplus t)-1.$

The same argument for the other side yields

$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$

Step 4: Boundary Conditions and the Meaning of \(-1\)

The bookkeeping state is what makes the recurrence clean. There is exactly one way to delete a whole attached branch: cut its attachment edge. Therefore

$C_n(-1)=1\qquad \text{for every } n\ge 1.$

Targets below \(-1\) are impossible, so

$C_n(t)=0\qquad \text{for } t<-1.$

For the smallest trees:

$C_1(t)=0\qquad \text{for } t\ge 0,$

because a single vertex has no edge to cut, and

$C_2(0)=1,\qquad C_2(t)=0\ \text{for } t\ne 0,$

because \(T_2\) has exactly one edge, and cutting it leaves a single vertex whose Grundy value is \(0\).

The desired counting function is therefore

$\boxed{f(k)=C_k(0).}$

Step 5: Worked Example for \(k=5\)

Using \(G_1=0\), \(G_2=1\), \(G_3=3\), \(G_4=6\), compute the needed auxiliary values:

$C_3(0)=C_1(1)+C_2(0)=0+1=1,$

$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$

$C_4(3)=C_2(6)+C_3(0)=0+1=1.$

Now evaluate

$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$

This agrees with the small checkpoint used by the implementation. Another checkpoint is \(f(10)=17\).

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they precompute the sequence \(G_n\) up to the requested \(k\). Then they evaluate the recurrence for \(C_n(t)\) with memoization: for each tree order \(n\), they store only those target values \(t\) that are actually reached. That sparse storage is important because the reachable targets form a small subset of all integers.

Each state is computed once, reduced modulo \(10^{18}\), and reused whenever it reappears. The final value returned is \(C_k(0)\), formatted as the last 18 digits.

Complexity Analysis

Let \(S_n\) be the number of distinct target values \(t\) that are actually visited for tree order \(n\). Precomputing the Grundy sequence costs \(O(k)\) time and \(O(k)\) memory. The memoized recursion computes each reachable pair \((n,t)\) once, so the counting stage costs

$O\!\left(\sum_{n=1}^{k} S_n\right)$

time and the same order of memory, up to the constant factors of associative-table lookups. This is dramatically smaller than expanding the full game tree of all possible cuts and resulting positions.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=400
2. Sprague-Grundy theorem: Wikipedia - Sprague-Grundy theorem
3. Nim and nim-sum: Wikipedia - Nim
4. Exclusive OR: Wikipedia - Exclusive OR
5. Fibonacci numbers: Wikipedia - Fibonacci number