CF1864H Asterism Stream

Bogocubic 正在和 amenotiomoi 玩一个游戏。首先，Bogocubic 固定了一个整数 $n$，然后他给 amenotiomoi 一个整数 $x$，初始时 $x=1$。 每一步，amenotiomoi 以相同的概率执行以下两种操作之一： - 将 $x$ 增加 $1$； - 将 $x$ 乘以 $2$。 Bogocubic 想要知道，amenotiomoi 需要进行多少步操作，才能使 $x$ 大于等于 $n$ 的期望步数。请你帮他计算这个期望步数对 $998\,244\,353$ 取模的结果。 形式化地，设 $M=998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。请输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $y$，满足 $0 \le y < M$ 且 $y \cdot q \equiv p \pmod{M}$。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。 接下来每个测试用例一行，包含一个整数 $n$（$1 \le n \le 10^{18}$）。

对于每个测试用例，输出一个整数，表示期望步数对 $998\,244\,353$ 取模的结果。

在第一个测试用例中，$n\le x$，无需任何操作，所以答案为 $0$。 在第二个测试用例中，对于 $n=4$，所有可能的操作序列及其概率如下： - $1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$，概率为 $\frac{1}{8}$； - $1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$，概率为 $\frac{1}{8}$； - $1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$，概率为 $\frac{1}{8}$； - $1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$，概率为 $\frac{1}{8}$； - $1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$，概率为 $\frac{1}{4}$； - $1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$，概率为 $\frac{1}{4}$。 因此，期望步数为 $4 \cdot \left(3 \cdot \frac{1}{8}\right) + 2 \cdot \left(2 \cdot \frac{1}{4} \right) =\frac{5}{2} \equiv 499122179 \pmod{998244353}$。 在第三个测试用例中，对于 $n=8$，期望步数为 $\frac{137}{32}\equiv 717488133\pmod{998244353}$。 在第四个测试用例中，对于 $n=15$，期望步数为 $\frac{24977}{4096} \equiv 900515847 \pmod{998244353}$。 由 ChatGPT 4.1 翻译