https://iq.opengenus.org/palindromic-tree-eertree/

Use custom allocator with fixed 128 Node.

struct NodeAllocator
{
    Node nodes[128];
    int pos = 0;
    Node* allocate() {
        assert(pos < 128);
        return nodes + (pos++);
    }

};


std::uint64_t rich_number(std::uint64_t val, int pos, int n, EerTree& tree)
{
    if (pos >= n) return 1;
    std::int64_t res = 0;
    for (std::uint64_t bit = 0; bit < 2; ++bit)
    {
        std::uint64_t s = val | (bit << pos);
        /********************************************/
        Node* t_current = tree.current;
        int t_pos = tree.alloc.pos;
        /********************************************/

        int r = tree.insert(s, pos);

        /********************************************/
        Node* cur_change = tree.cur_change;
        /********************************************/

        if (r == 1) {
            res += rich_number(s, pos + 1, n, tree);
        }


        /********************************************/
        //reset tree insert back
        tree.current = t_current;
        tree.alloc.pos = t_pos;
        if (r==1){
            cur_change->labeled[bit] = nullptr;
        }
        /********************************************/
    }

    return res;
}

------------
rich_number(0, 0, 61) -> gives  61-rich palindrome.


My computer it runs 52 hours.