AT_utpc2023_h.Huge Segment Tree

我们用整数 $i, j$（$0 \leq i \leq K, 0 \leq j < 2^{K-i}$）来表示区间 $[2^i j, 2^i (j+1))$，并将这样的区间称为线段树型区间。

对于整数 $l, r$（$0 \leq l < r \leq 2^K$），可以证明区间 $[l, r)$ 总能唯一地表示为若干个线段树型区间的并。记在这种表示下所用区间的最小个数为 $f(l, r)$。

请针对 $k = 1, 2, \dots, 2K-2$，分别解答以下问题：

求满足 $f(l, r)=k$ 的整数对 $l, r$（$0 \leq l < r \leq 2^K$）有多少组。请将答案对 $998244353$ 取模输出。

输入为如下格式，通过标准输入给出。

$K$

请按顺序输出 $k=1,2,\dots,2K-2$ 时的问题答案，用空格分隔。

样例说明 1

例如 $k = 4$ 时，只有 $l=1, r=7$ 满足 $f(l, r)=k$，所以输出 $1$。

数据范围

• 输入为整数
• $2 \leq K \leq 5 \times 10^5$

由 ChatGPT 5 翻译