Problem 400: Fibonacci Tree Game

Project Euler Problem 400 Solution

EulerSolve provides an optimized solution for Project Euler Problem 400, Fibonacci Tree Game, with C++, Python, Java, and a step-by-step mathematical explanation.

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)$....

Detailed mathematical approach

Problem Summary

The Fibonacci tree of order $k$, written $T(k)$, is defined recursively: $T(0)$ is the empty tree, $T(1)$ is the binary tree with a single node, and for $k\ge2$ the root of $T(k)$ has $T(k-1)$ and $T(k-2)$ as its children. Two players play a take-away game on $T(k)$: a turn selects a node and removes it together with the subtree rooted at it, and the player who is forced to take the root node of the entire tree loses. Let $f(k)$ be the number of winning first moves of the first player, that is, the moves after which the second player has no winning strategy. The statement gives $f(5)=1$ and $f(10)=17$, and asks for the last $18$ digits of $f(10000)$. ^[1]

Counting nodes gives $|T(k)|=F(k+2)-1$ with $F(1)=F(2)=1$, so the sizes are $1,2,4,7,12,20,33,54,\dots$ ^[7] Because $F(n)$ grows like $\varphi^n/\sqrt5$ with $\varphi=(1+\sqrt5)/2$, ^[8] the tree $T(10000)$ has a $2090$-digit number of nodes: neither its nodes nor the positions of the game can be enumerated.

The whole solution in one sentence: summarise the game on every Fibonacci tree by one number, computed from the numbers of the two smaller trees, and then count the winning cuts by a recursion over the orders that remembers which number the cut branch must be left with.

Mathematical Approach

1. The rules in terms of edges

Removing a node other than the root, with its subtree, is the same as cutting the single edge that joins it to its parent: everything above the cut falls away. Taking the root ends the game at once and loses, so a player does it only when the root is all that is left. The game is therefore this one: the players alternately cut an edge and the player who cannot cut loses — the standard “normal play” convention, here Green Hackenbush on a tree whose root is on the ground. ^[5] ^[6]

For $k\le7$ we checked by complete search that the two readings of the rule — taking the root as a legal but losing move, or only when it is the last node — give the same winner and the same winning moves.

2. Three small trees by hand

$T(1)$ is a single node with no edge: the first player must take the root and loses, so $f(1)=0$. $T(2)$ is a root with one child, its second child $T(0)$ being empty; cutting that one edge leaves the bare root for the opponent, so $f(2)=1$.

$T(3)$ has four nodes and three edges: the root $r$, the root $a$ of the $T(2)$ branch, the leaf $b$ below $a$, and the leaf $c$ of the $T(1)$ branch. All three first cuts can be followed by hand.

Cutting $a$ removes $a$ and $b$, leaving the single edge $r$–$c$; the opponent cuts it and we must take the root: we lose.
Cutting $b$ leaves two single edges below $r$; whichever the opponent cuts, we cut the other and the opponent faces the bare root: we win.
Cutting $c$ leaves the path $r$–$a$–$b$; the opponent cuts $r$–$a$, removing both, and again we must take the root: we lose.

So $f(3)=1$. Two lessons are already visible: equal branches cancel, because the second player can mirror every move, and a path behaves like a Nim heap of counters.

3. Grundy values

Every move removes a node, so the game is finite and has no draws, and both players always have the same moves: it is an impartial game under normal play. Such a game has a Grundy value $G$, the smallest non-negative integer that is not the value of any position reachable in one move — the minimum excluded value, $\operatorname{mex}$. ^[4] For example $\operatorname{mex}\{0,1,3\}=2$, and the mex of the empty set is $0$, so a position with no legal move, here the bare root, has Grundy value $0$. The player to move loses against correct play exactly when the value is $0$. ^[2]

Two consequences of the definition are used repeatedly below. If a position has value $s$, then for every $u$ with $0\le u\lt s$ some move leads to a position of value $u$, and no move leads to value $s$. Hence the winning moves are exactly the moves to a position of value $0$, and there are none when the position itself has value $0$: so $f(k)=0$ exactly when $G(T(k))=0$.

4. Branches are independent

After any number of cuts the position is still the root with some branches hanging from it, and a cut touches only one branch. The game is therefore the disjunctive sum of the games played on the separate branches, and the Grundy value of a sum is the nim-sum of the summands, that is, the bitwise exclusive-or $\oplus$ of their Grundy values: write the numbers in binary and put a $1$ where their digits differ, so $3=(11)_2$ and $1=(01)_2$ give $3\oplus1=(10)_2=2$, while equal values cancel. ^[2] ^[3] A path of $n$ edges is literally a one-pile Nim game — a cut leaves a shorter path of any length $0,\dots,n-1$ — so its Grundy value is $n$. ^[4]

We need two values per rooted tree $X$: let $G(X)$ be the Grundy value of the game on $X$ with its root on the ground, and $B(X)$ that of the branch game, the same tree hanging from an edge, in which every node may be cut, its own root included, whose removal makes the branch disappear. By the previous paragraph $G(X)$ is the exclusive-or of the values $B$ of the branches of $X$.

5. The branch lemma

The fact that turns the tree into arithmetic is this lemma, a special case of the colon principle of Hackenbush theory. ^[5]

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

Proof. Induction on the number of nodes of $X$. Let $X$ have branches $X_1,\dots,X_m$ and put $s=G(X)=B(X_1)\oplus\cdots\oplus B(X_m)$. A move in the branch game either cuts the branch away, leaving the empty position of value $0$, or cuts inside some $X_i$. A cut inside $X_i$ leaves a smaller tree $X'$ still hanging from its edge, so by the induction hypothesis the resulting position has value $G(X')+1$, and $G(X')$ is exactly the value that same cut reaches in the game on $X$ with the root on the ground. By Section 3 those values cover every $u$ with $0\le u\lt s$ and never equal $s$. The options therefore have the values $\{0\}\cup\{1+u\}$, which cover $0,1,\dots,s$ and omit $s+1$, so the $\operatorname{mex}$ is $s+1$. $\square$

Combining the lemma with Section 4 gives the rule that computes any rooted tree from its branches:

$$G(X)=\bigoplus_{i=1}^{m}\bigl(1+G(X_i)\bigr).$$

The two single edges of Section 2 give $1\oplus1=0$ again, the mirror strategy. We also checked the rule against the plain $\operatorname{mex}$ definition on all $528\,705$ positions reachable from $T(7)$, nodes distinguished by their place in the tree.

6. The Grundy value of the Fibonacci tree

Write $G_k=G(T(k))$. The single node gives $G_1=0$; $T(2)$ has one branch, a single node, so $G_2=0+1=1$. For $k\ge3$ the root has the two branches $T(k-1)$ and $T(k-2)$, so the lemma gives

$$G_k=(1+G_{k-1})\oplus(1+G_{k-2}).$$

The first values, one exclusive-or per order, are

$$0,1,3,6,3,3,0,5,7,14,7,7,0,9,\dots$$

for $k=1,2,\dots,14$. For instance $G_4=(1+3)\oplus(1+1)=4\oplus2=6$ and $G_5=(1+6)\oplus(1+3)=7\oplus4=3$.

7. A pattern in groups of six

The zeros at $k=1,7,13$ are not an accident. For every $m\ge0$,

$$\begin{aligned}G_{6m+1}&=0,\qquad G_{6m+2}=4m+1,\\G_{6m+3}&=G_{6m+5}=G_{6m+6}=4m+3,\\G_{6m+4}&=(4m+2)\oplus(4m+4).\end{aligned}$$

Proof. Induction on $m$. The case $m=0$ holds: $G_1=0$ and $G_2=1$. Assume $G_{6m+1}=0$ and $G_{6m+2}=4m+1$, and write $c=(4m+2)\oplus(4m+4)$. Only two facts are needed: $x\oplus x=0$, and $x+1=x\oplus1$ for even $x$, whose last bit is free. Applying the recurrence six times gives

$$\begin{aligned}G_{6m+3}&=(4m+2)\oplus1=4m+3,\\G_{6m+4}&=(4m+4)\oplus(4m+2)=c,\\G_{6m+5}&=(c+1)\oplus(4m+4)\\&=4m+3,\\G_{6m+6}&=(4m+4)\oplus(c+1)\\&=4m+3,\\G_{6m+7}&=(4m+4)\oplus(4m+4)=0,\\G_{6m+8}&=1\oplus(4m+4)=4m+5.\end{aligned}$$

In the third and fourth lines $c$ is even, so $c+1=c\oplus1$; one copy of $4m+4$ then cancels and $(4m+2)\oplus1=4m+3$ is left. The last two lines are the hypothesis for $m+1$, because $4m+5=4(m+1)+1$. $\square$

So the second player wins on $T(k)$ exactly when $k\equiv1\pmod 6$, and by Section 3 those are exactly the orders with $f(k)=0$, as $f(7)=f(13)=f(19)=0$ confirm. Since $10000=6\cdot1666+4$, the first player wins on $T(10000)$, whose Grundy value is $6666\oplus6668=6$.

The orders $k\equiv4\pmod 6$ are the only irregular ones: with $w=2m+1$, shifting out the common factor gives $G_{6m+4}=2\bigl(w\oplus(w+1)\bigr)$. If $w$ ends in $j$ one-bits, adding $1$ flips exactly those bits and the next one, so $w\oplus(w+1)=2^{j+1}-1$; and $w\ge2^j-1$ gives $2^{j+1}-1\le2w+1$, hence $G_{6m+4}\le8m+6$. Every other case of the formula is at most $\tfrac23k+1$, so $G_k\le\tfrac43k+1$ throughout. The spikes stay moderate: for $k\le10000$ we have $w\le3333$, the most trailing ones occur at $w=2047$, and the largest value is $G_{6142}=2(2^{12}-1)=8190$.

8. Counting the winning moves

A single number per order is not enough: we must count cuts, not evaluate one position. Counting works because a cut inside a branch changes only that branch, and that branch is a Fibonacci tree of known order. For $n\ge1$ and an integer $t$, let $C_n(t)$ be the number of nodes of $T(n)$ whose removal leaves a tree of Grundy value $t$, with the removal of the root of $T(n)$ itself recorded as the bookkeeping case $t=-1$: the branch is then gone and contributes $0=(-1)+1$. The lemma of Section 5 then reads “a branch in state $u$ contributes $1+u$” in all cases.

Let $n\ge3$ and $t\ge0$. A cut inside $T(n)$ lies in the $T(n-1)$ branch or in the $T(n-2)$ branch, never both, and the untouched branch keeps its contribution. If the cut leaves the $T(n-1)$ branch in state $u_l$, then

$$t=(1+u_l)\oplus(1+G_{n-2}),$$

and since $\oplus$ is its own inverse this fixes $u_l$. The same step on the other side gives the recurrence

$$C_n(t)=C_{n-1}(u_l)+C_{n-2}(u_r)$$

with

$$\begin{aligned}u_l&=\bigl((1+G_{n-2})\oplus t\bigr)-1,\\u_r&=\bigl((1+G_{n-1})\oplus t\bigr)-1.\end{aligned}$$

The boundary cases finish the definition. Exactly one cut deletes a whole branch, namely its own edge, so $C_n(-1)=1$ for every $n\ge1$, and a contribution is never negative, so $C_n(t)=0$ for $t\le-2$. $T(1)$ has nothing below its root, so $C_1(t)=0$ for $t\ge0$; $T(2)$ has one node below its root, whose removal leaves a bare root, so $C_2(0)=1$ and $C_2(t)=0$ for every other $t\ge0$. The answer is

$$f(k)=C_k(0),$$

which correctly excludes the root of the whole tree, since taking it would need the target $-1$. Finally $C_n(t)$ depends only on $n$ and $t$, because all copies of $T(n)$ in the big tree are identical — that is what makes the recursion affordable.

9. Worked example: $f(5)=1$ and $f(6)=3$

With $G_1,\dots,G_4=0,1,3,6$ the recursion for $k=5$ asks for $u_l=\bigl((1+G_3)\oplus0\bigr)-1=3$ and $u_r=\bigl((1+G_4)\oplus0\bigr)-1=6$, so

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

Unfolding the first term, $C_4(3)=C_3(0)+C_2(6)=1+0$ and $C_3(0)=C_2(0)+C_1(1)=1+0$, so the one surviving path ends at the node counted by $C_2(0)$. Followed through the tree, that node is the leaf at the end of the all-left spine of $T(5)$: the unique node at depth $4$ of a tree with $12$ nodes.

The arithmetic can be checked by hand. In $T(5)$ the branches contribute $1+G_4=7$ and $1+G_3=4$, and indeed $7\oplus4=3=G_5$. Cutting the deepest leaf turns the innermost $T(2)$ into a bare node, so it contributes $1$ instead of $2$; the $T(3)$ above it becomes $1\oplus1=0$ and contributes $1$ instead of $4$; the $T(4)$ above that becomes $1\oplus2=3$ and contributes $4$ instead of $7$; and the whole tree becomes $4\oplus4=0$. The opponent is left with a lost position.

For $k=6$ the same step gives $f(6)=C_5(6)+C_4(3)=2+1=3$ with $C_5(6)=C_4(1)+C_3(0)=1+1$: two winning cuts in the $T(5)$ branch, one in the $T(4)$ branch. A complete search of $T(6)$ finds exactly those three moves, all leaves at depth $4$, and the checkpoint $f(10)=17$ comes out of the same recursion.

10. Why the table stays small

Written as a plain recursion, $C_k(0)$ branches in two at every step, so the number of paths grows like $F(k)$; memoisation collapses it, because each pair $(n,t)$ is evaluated once and the pairs are few. Every stored target satisfies $t\ge0$, and if $t$ and all values $1+G_n$ are below $2^{13}$ then so is $\bigl((1+G_n)\oplus t\bigr)-1$; as the largest Grundy value for $k\le10000$ is $8190$, every target lies in $\{0,1,\dots,8190\}$.

For $k=10000$ we measured $16\,734\,773$ stored pairs, at most $2048$ for any single order, and at most $5046$ simultaneously active calls. The nesting stays near $k/2$ because order $n-2$ is visited before order $n-1$: along the deepest chain measured, $4953$ steps lower the order by two and only $91$ by one. That is a property of this traversal, not a bound — single-step calls do miss the cache elsewhere, $8\,367\,385$ times in all — while the general bound is $O(k)$, since every call lowers the order.

11. The last eighteen digits

The exact $f(10000)$ has $2087$ decimal digits, so the statement asks only for $f(10000)\bmod10^{18}$. This loses nothing: the recursion only ever adds counts, never subtracts or compares them, so every value may be reduced modulo $10^{18}$ at once. Two residues below $10^{18}$ add to less than $2\cdot10^{18}$, itself below $2^{63}$, so the reduction is one conditional subtraction, with no wide arithmetic. The digits are printed with leading zeros, which the last $18$ digits may need.

How the Code Works

The C++ program ^[10] reads its parameters in parse_arguments, which accepts --k= for the order and --skip-checkpoints and rejects an order below $1$. Unless they are skipped, run_checkpoints verifies $f(5)=1$ and $f(10)=17$ before the real computation.

The work is done by Solver400, whose constructor fills the array sg with the Grundy values of Section 6 from sg[1] = 0 and sg[2] = 1, one exclusive-or per order. Its member prune(tree_size, target) is the recursion of Section 8, with the four boundary cases in the same order: $t=-1$ gives $1$, $t\le-2$ gives $0$, order $1$ gives $0$, order $2$ gives $1$ only for $t=0$. Otherwise it derives right_target and left_target from sg, recurses on tree_size - 2 and tree_size - 1, adds the two counts with one conditional subtraction of $10^{18}$ and stores it. Then f_mod returns prune(k, 0) and main prints $18$ digits padded with zeros.

Each order owns its memo table, a FlatMap: an open-addressing hash table with linear probing, a power-of-two capacity, a growth threshold at $70\%$ occupancy, the key $\mathtt{0xFFFFFFFF}$ reserved for an empty slot, and an integer mixing function as its hash. Its keys are $32$-bit targets and its values $64$-bit counts, which makes this version the most frugal of the three.

The Python version is the same recursion with a list of dictionaries and % MOD; it raises the interpreter limit with sys.setrecursionlimit(50000), the default being far below the depth reached here, ^[9] and formats with zfill(18). The Java version keeps one HashMap<Integer, Long> per order, repeats the conditional subtraction, prints with String.format("%018d") and asks for a call stack of $2^{26}$ bytes rather than the platform default, a request the virtual machine may adjust or ignore. Both fix the order at $10000$ and skip the checkpoints; only C++ takes an order on the command line.

Complexity and Verification

Filling the Grundy array costs $O(k)$ time and memory. Let $S$ be the number of stored pairs $(n,t)$. Each new pair costs one failed lookup, two recursive calls, two exclusive-ors, one addition and one insertion, so with the usual expected-constant-time hashing the counting stage runs in $O(k+S)$ time, and the arrays, the table and the nesting take $O(k+S)$ space. Section 10 gives $S\le8191k$ for $k=10000$, with $S=16\,734\,773$ in fact; since all Grundy values up to order $k$ are $O(k)$, the general bound is $S=O(k^2)$. Every entry is kept to the end, and the measured peak resident sizes were about $453$ MB for C++, $1.7$ GB for Python and $1.9$ GB for Java, the difference coming from a flat table of $32$-bit keys and $64$-bit values against dictionaries and boxed Integer and Long objects. The three programs took about $0.9$ s, $6.7$ s and $1.3$ s on one machine, the C++ at optimisation level 2, and printed identical digits.

Beyond the checkpoints packaged in C++, these checks were run for this article.

A complete search of the game, using only the rules and the $\operatorname{mex}$ definition, reproduces $f(k)=0,1,1,1,1,3,0$ for $k=1,\dots,7$, and confirms the branch rule of Section 5 on all $528\,705$ positions reachable from $T(7)$.
An independent count that prunes each of the $F(k+2)-1$ nodes in turn and recomputes the Grundy value along the path to the root, without the target recursion, agrees with $C_k(0)$ for every $k\le25$; for example $f(20)=1383$ and $f(24)=7945$.
The closed form of Section 7 agrees with the recurrence for every $k\le20000$, with zeros exactly at $k\equiv1\pmod 6$.

These cross-checks are not part of the published programs, which check only $f(5)$ and $f(10)$, in C++.

Footnotes and References

The references below supply the background facts used above; the branch lemma, the pattern of the Grundy values in groups of six, the counting recurrence and the state counts are derived or measured in this article.

Project Euler 400 — Fibonacci Tree Game. The official statement defines the Fibonacci tree T(k) recursively, lets two players remove a node with the subtree rooted at it until one is forced to take the root node of the entire tree and loses, defines f(k) as the number of winning first moves, gives f(5) = 1 and f(10) = 17, and asks for the last 18 digits of f(10000).
Wikipedia — Sprague–Grundy theorem. Every impartial game under normal play equals one nimber, its Grundy value; a position's value is the mex of its options' values; a sum of positions has the nim-sum of their values; and a position is a loss for the player to move exactly when its value is zero.
Wikipedia — Nim. The nim-sum is the binary digital sum of the heap sizes without carries, that is, the bitwise exclusive-or written $\oplus$ here, and the first player of Nim wins exactly when the nim-sum of the heaps is nonzero.
Wikipedia — mex (minimum excludant). The mex of a subset is the smallest value of the ground set it does not contain; a position with no legal move has nimber 0, any other the mex of its options' nimbers; and a one-pile Nim heap of n stones has nimber n, the fact used for paths in Section 4.
Wikipedia — Hackenbush. In Green Hackenbush either player may cut any edge, so the game is impartial; with plain stalks it is Nim; and by the colon principle the branches meeting at a vertex may be replaced by one stalk whose length is their nim-sum. Section 5 proves the case used here.
Wikipedia — Winning Ways for Your Mathematical Plays. The book by Elwyn Berlekamp, John Conway and Richard Guy that developed combinatorial game theory, Sprague–Grundy theory included; the article lists Green Hackenbush as a form of Nim.
OEIS A000071. The sequence a(n) = Fibonacci(n) − 1, whose terms 1, 2, 4, 7, 12, 20, 33, 54 are the node counts used in the summary. It also records that a(n+2) is the least number of elements in an AVL tree of height n, the classical reason Fibonacci trees appear in computer science.
Wikipedia — Fibonacci sequence. The recurrence F(n) = F(n−1) + F(n−2), the older convention F(1) = F(2) = 1 used here, and the asymptotics F(n) ~ φⁿ/√5 from Binet's formula, which give the digit count of the node number of T(10000).
Python documentation — sys.setrecursionlimit. The limit stops runaway recursion from overflowing the C stack, its highest usable value is platform-dependent, and raising it needs care; the Python version raises it to 50000.
C++ — Euler400.cpp. The linked immutable revision contains Solver400 with its Grundy array and prune, the FlatMap memo tables and the checkpoints for f(5) and f(10). It is the implementation record for this article.

Problem 400 source code

C++

#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
constexpr u64 kMod = 1000000000000000000ULL;  // last 18 digits

struct Options {
    int k = 10000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = std::stoi(tail);
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--k=", options.k)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.k >= 1;
}

inline u64 add_mod(u64 a, u64 b) {
    u64 s = a + b;
    if (s >= kMod) {
        s -= kMod;
    }
    return s;
}

struct FlatMap {
    std::vector<std::uint32_t> keys;
    std::vector<u64> values;
    std::size_t used = 0;

    static constexpr std::uint32_t kEmpty = 0xFFFFFFFFu;

    static std::uint32_t hash(std::uint32_t x) {
        x ^= x >> 16;
        x *= 0x7feb352d;
        x ^= x >> 15;
        x *= 0x846ca68b;
        x ^= x >> 16;
        return x;
    }

    void rehash(std::size_t cap) {
        std::vector<std::uint32_t> old_keys = std::move(keys);
        std::vector<u64> old_values = std::move(values);
        keys.assign(cap, kEmpty);
        values.assign(cap, 0);
        used = 0;
        for (std::size_t i = 0; i < old_keys.size(); ++i) {
            if (old_keys[i] != kEmpty) {
                insert(old_keys[i], old_values[i]);
            }
        }
    }

    bool get(std::uint32_t key, u64& out) const {
        if (keys.empty()) {
            return false;
        }
        const std::size_t mask = keys.size() - 1;
        std::size_t idx = hash(key) & mask;
        while (true) {
            const std::uint32_t cur = keys[idx];
            if (cur == kEmpty) {
                return false;
            }
            if (cur == key) {
                out = values[idx];
                return true;
            }
            idx = (idx + 1) & mask;
        }
    }

    void insert(std::uint32_t key, u64 value) {
        if (keys.empty() || (used + 1) * 10 >= keys.size() * 7) {
            const std::size_t next = keys.empty() ? 64 : keys.size() * 2;
            rehash(next);
        }
        const std::size_t mask = keys.size() - 1;
        std::size_t idx = hash(key) & mask;
        while (true) {
            const std::uint32_t cur = keys[idx];
            if (cur == kEmpty) {
                keys[idx] = key;
                values[idx] = value;
                ++used;
                return;
            }
            if (cur == key) {
                values[idx] = value;
                return;
            }
            idx = (idx + 1) & mask;
        }
    }
};

struct Solver400 {
    int n = 0;
    std::vector<int> sg;
    std::vector<FlatMap> cache;
    u64 nodes = 0;

    explicit Solver400(int n) : n(n), sg(n + 1, 0), cache(n + 1) {
        if (n >= 1) {
            sg[1] = 0;
        }
        if (n >= 2) {
            sg[2] = 1;
        }
        for (int i = 3; i <= n; ++i) {
            sg[i] = (1 + sg[i - 1]) ^ (1 + sg[i - 2]);
        }
    }

    u64 prune(int tree_size, int target) {
        if (target == -1) {
            return 1;
        }
        if (target < -1) {
            return 0;
        }
        if (tree_size == 1) {
            return 0;
        }
        if (tree_size == 2) {
            return target == 0 ? 1 : 0;
        }

        FlatMap& memo = cache[tree_size];
        u64 cached = 0;
        if (memo.get(static_cast<std::uint32_t>(target), cached)) {
            return cached;
        }

        ++nodes;
        const int right_target = ((sg[tree_size - 1] + 1) ^ target) - 1;
        const int left_target = ((sg[tree_size - 2] + 1) ^ target) - 1;
        const u64 right = prune(tree_size - 2, right_target);
        const u64 left = prune(tree_size - 1, left_target);
        u64 res = right + left;
        if (res >= kMod) {
            res -= kMod;
        }
        memo.insert(static_cast<std::uint32_t>(target), res);
        return res;
    }
};

u64 f_mod(const int target_k) {
    Solver400 solver(target_k);
    return solver.prune(target_k, 0);
}

bool run_checkpoints() {
    if (f_mod(5) != 1ULL) {
        std::cerr << "Checkpoint failed: f(5)\n";
        return false;
    }
    if (f_mod(10) != 17ULL) {
        std::cerr << "Checkpoint failed: f(10)\n";
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const u64 answer = f_mod(options.k);
    std::cout << std::setfill('0') << std::setw(18) << answer << '\n';
    return 0;
}

Python

def solve():
    MOD = 10**18
    K = 10000
    sg = [0] * (K + 1)
    if K >= 2: sg[2] = 1
    for i in range(3, K + 1):
        sg[i] = (1 + sg[i-1]) ^ (1 + sg[i-2])

    cache = [dict() for _ in range(K + 1)]

    def prune(ts, target):
        if target == -1: return 1
        if target < -1: return 0
        if ts == 1: return 0
        if ts == 2: return 1 if target == 0 else 0
        if target in cache[ts]: return cache[ts][target]
        rt = ((sg[ts-1] + 1) ^ target) - 1
        lt = ((sg[ts-2] + 1) ^ target) - 1
        res = (prune(ts-2, rt) + prune(ts-1, lt)) % MOD
        cache[ts][target] = res
        return res

    import sys
    sys.setrecursionlimit(50000)
    ans = prune(K, 0)
    return str(ans).zfill(18)

if __name__ == '__main__':
    print(solve())

Java

import java.util.HashMap;
import java.util.Map;

public class Euler400 {
    static final long K_MOD = 1000000000000000000L;

    static class Solver400Impl {
        int n;
        int[] sg;
        Map<Integer, Long>[] cache;

        @SuppressWarnings("unchecked")
        Solver400Impl(int n) {
            this.n = n;
            this.sg = new int[n + 1];
            this.cache = new Map[n + 1];

            for (int i = 0; i <= n; i++) {
                this.cache[i] = new HashMap<>();
            }

            if (n >= 1)
                sg[1] = 0;
            if (n >= 2)
                sg[2] = 1;

            for (int i = 3; i <= n; i++) {
                sg[i] = (1 + sg[i - 1]) ^ (1 + sg[i - 2]);
            }
        }

        long prune(int treeSize, int target) {
            if (target == -1)
                return 1;
            if (target < -1)
                return 0;
            if (treeSize == 1)
                return 0;
            if (treeSize == 2)
                return target == 0 ? 1 : 0;

            Map<Integer, Long> memo = cache[treeSize];
            Long cached = memo.get(target);
            if (cached != null) {
                return cached;
            }

            int rightTarget = ((sg[treeSize - 1] + 1) ^ target) - 1;
            int leftTarget = ((sg[treeSize - 2] + 1) ^ target) - 1;

            long right = prune(treeSize - 2, rightTarget);
            long left = prune(treeSize - 1, leftTarget);

            long res = right + left;
            if (res >= K_MOD)
                res -= K_MOD;

            memo.put(target, res);
            return res;
        }
    }

    static String solve() {
        int k = 10000;
        Solver400Impl solver = new Solver400Impl(k);
        long ans = solver.prune(k, 0);
        return String.format("%018d", ans);
    }

    public static void main(String[] args) throws InterruptedException {
        String[] result = new String[1];
        Thread t = new Thread(null, () -> {
            result[0] = solve();
        }, "Solver", 1 << 26);
        t.start();
        t.join();
        System.out.println(result[0]);
    }
}