AT_pakencamp_2024_day1_q Large Heap 2

记下列问题的答案为 $f(K)$。 > 考虑 $(1,2,\ldots,K)$ 的一个排列 $P = (P_{1}, P_{2}, \ldots, P_{K})$。当 $P$ 满足以下所有条件时，称之为 **堆状的** 排列： > > - $2P_{i} \leq P_{2i}$（$1 \leq i \leq \left\lfloor \frac{K}{2} \right\rfloor$） > - $2P_{i} \leq P_{2i+1}$（$1 \leq i \leq \left\lfloor \frac{K-1}{2} \right\rfloor$） > > 请你求出所有堆状排列的个数。 给定 $N$，请计算 $f(1)+f(2)+\cdots+f(N)$，并输出其除以 $998244353$ 的余数。 每组输入包含 $T$ 个测试用例。

输入通过标准输入，格式如下： > $T$ $\mathrm{case}_{1}$ $\mathrm{case}_{2}$ $\vdots$ $\mathrm{case}_{T}$ 每个测试用例包含以下格式： > $N$

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

### 示例说明 1 例如当 $K=5$ 时，$P=\lbrace 1,2,3,5,4 \rbrace$ 是一个堆状排列。 ### 数据范围 - $1 \leq T \leq 10^{6}$ - $1 \leq N \leq 10^{18}$ - 所有输入均为整数。 由 ChatGPT 5 翻译