CF1237E.Balanced Binary Search Trees

Recall that a binary search tree is a rooted binary tree, whose nodes each store a key and each have at most two distinguished subtrees, left and right. The key in each node must be greater than any key stored in the left subtree, and less than any key stored in the right subtree.

The depth of a vertex is the number of edges on the simple path from the vertex to the root. In particular, the depth of the root is $0$.

Let's call a binary search tree perfectly balanced if there doesn't exist a binary search tree with the same number of vertices that has a strictly smaller sum of depths of its vertices.

Let's call a binary search tree with integer keys striped if both of the following conditions are satisfied for every vertex $v$:

• If $v$ has a left subtree whose root is $u$, then the parity of the key of $v$ is different from the parity of the key of $u$.
• If $v$ has a right subtree whose root is $w$, then the parity of the key of $v$ is the same as the parity of the key of $w$.

You are given a single integer $n$. Find the number of perfectly balanced striped binary search trees with $n$ vertices that have distinct integer keys between $1$ and $n$, inclusive. Output this number modulo $998\,244\,353$.

回忆一下，二叉搜索树（BST）是一棵有根的二叉树，其每个节点存储一个键值，且最多有两个被特别区分的子树：左子树和右子树。每个节点中的键值必须大于其左子树中任意节点的键值，且小于其右子树中任意节点的键值。

一个顶点的深度定义为该顶点到树根的简单路径上的边数。特别地，根节点的深度为 $0$。

我们称一棵二叉搜索树是完美平衡的，当且仅当不存在另一棵具有相同顶点数的二叉搜索树，其所有顶点的深度之和严格更小。

我们称一棵键值为整数的二叉搜索树是条纹状的（striped），当且仅当对每个顶点 $v$ 均满足以下两个条件：

• 若 $v$ 有左子树，且其左子树的根为 $u$，则 $v$ 的键值的奇偶性与 $u$ 的键值的奇偶性不同；
• 若 $v$ 有右子树，且其右子树的根为 $w$，则 $v$ 的键值的奇偶性与 $w$ 的键值的奇偶性相同。

给定一个整数 $n$。请计算满足以下条件的完美平衡的条纹状二叉搜索树的个数：

• 共有 $n$ 个顶点；
• 所有键值为 $1$ 到 $n$（含）之间的互不相同的整数。

将结果对 $998\,244\,353$ 取模后输出。

The only line contains a single integer $n$ ($1 \le n \le 10^6$), denoting the required number of vertices.

唯一的一行包含一个整数 $n$（$1 \le n \le 10^6$），表示所需的顶点数。

Output the number of perfectly balanced striped binary search trees with $n$ vertices and distinct integer keys between $1$ and $n$, inclusive, modulo $998\,244\,353$.

输出具有 $n$ 个顶点、且键值为 $1$ 到 $n$（含）之间的互异整数的完美平衡的条纹二叉搜索树的数量，结果对 $998\,244\,353$ 取模。

In the first example, this is the only tree that satisfies the conditions:

In the second example, here are various trees that don't satisfy some condition:

在第一个例子中，这是唯一一棵满足条件的树：

在第二个例子中，以下是若干不满足某条条件的树：