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.
