← 返回题目列表

AtCoder · pakencamp_2024_day1_q

Q. 大堆 2

中文机器翻译题面 查看原题

配点 : 600 点

問題文

回答以下问题 f(K) 。

(1,2,\ldots,K) 的排列 给出了 P=(P_{1},P_{2}, \ldots ,P_{K}) 。 P 满足以下所有条件时, 类似堆 我们称之为排列。

  • 2P_{i} \leq P_{2i} \left(1 \leq i \leq \left\lfloor \frac{K}{2} \right\rfloor \right)

  • 2P_{i} \leq P_{2i+1} \left(1 \leq i \leq \left\lfloor \frac{K-1}{2} \right\rfloor \right)

求类堆排列的数量。

N ,所以 f(1)+f(2)+ \cdots +f(N) 该值应乘以 998244353 除以求余。

1 每个输入的测试用例是 有 T 件。

制約

  • 1 \leq T \leq 10^{6}
  • 1 \leq N \leq 10^{18}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}

每个测试用例均按以下格式给出。 打印

N

出力

T 行。 i 在线 i 个测试用例的答案。


入力例 1

3
6
1
1000

出力例 1

9
1
465040340

例如 第 K=5 时, P=\lbrace 1,2,3,5,4 \rbrace 是一个类似堆的排列。 01