Asterism Stream
Contest: Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
Difficulty rating: 3200
Tags: dp, math, matrices

Bogocubic is playing a game with amenotiomoi. First, Bogocubic fixed an integer $$$n$$$, and then he gave amenotiomoi an integer $$$x$$$ which is initially equal to $$$1$$$.

In one move amenotiomoi performs one of the following operations with the same probability:

- increase $$$x$$$ by $$$1$$$;
- multiply $$$x$$$ by $$$2$$$.

Bogocubic wants to find the expected number of moves amenotiomoi has to do to make $$$x$$$ greater than or equal to $$$n$$$. Help him find this number modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$y$$$ that $$$0 \le y < M$$$ and $$$y \cdot q \equiv p \pmod{M}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Output format:
For each test case, output a single integer — the expected number of moves modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$n\le x$$$ without any operations, so the answer is $$$0$$$.

In the second test case, for $$$n = 4$$$, here is the list of all possible sequences of operations and their probabilities:

- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$, the probability is $$$\frac{1}{8}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$, the probability is $$$\frac{1}{8}$$$;
- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$, the probability is $$$\frac{1}{8}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$, the probability is $$$\frac{1}{8}$$$;
- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$, the probability is $$$\frac{1}{4}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$, the probability is $$$\frac{1}{4}$$$.

So the expected number of moves is $$$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}$$$.

In the third test case, for $$$n = 8$$$, the expected number of moves is $$$\frac{137}{32}\equiv 717488133\pmod{998244353}$$$.

In the fourth test case, for $$$n = 15$$$, the expected number of moves is $$$\frac{24977}{4096} \equiv 900515847 \pmod{998244353}$$$.

Example input:
7
1
4
8
15
998244353
296574916252563317
494288321850420024

Example output:
0
499122179
717488133
900515847
93715054
44488799
520723508

Editorial:
Here is a basic $$$\Theta(n)$$$ dp solution.
Before that let $$$k = \frac{1}{2}$$$. At the same time, because a special geometric sequence $$$f(x)=ak^{bx}$$$ will be frequently used next, it is defined as $$$\{a,b\}$$$.
Let $$$f(x)$$$ be the expected number of moves needed if we start with $$$x$$$. Obviously, there is the following formula:
$$$$$$f(x)=\begin{cases}0&n\leqslant x\\k(f(x+1)+f(2x))+1&x<n\end{cases}$$$$$$
It's easy to see that for the interval $$$[n, 2n]$$$ value of $$$f(x)$$$ is $$$0$$$.
If for an interval $$$[2l,2r]$$$, it can already be represented by the sum of several $$$\{a,b\}$$$, then it can be represented by a small number of new $$$\{a,b\}$$$ for all $$$f(x)$$$, where $$$x\in[l,r]$$$
First there is $$$f(r)=kf(r+1)+kf(2r)+1$$$. So, $$$r-1$$$ can be represented as $$$f(r-1)=k^2f(r+1)+ kf(2r-2)+k^2f(2r)+k+1$$$.
By analogy, one can get
$$$$$$f(r-x)=k^{x+1}f(r+1)+\sum\limits_{i=0}^xk^{i+1}f(2r-2x+2i)+\sum\limits_{i=0}^xk^i$$$$$$
by substitution, it can be shown as
$$$$$$f(x)=k^{r-x+1}f(r+1)+\sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)+\sum\limits_{i=0}^{r-x}k^i$$$$$$
Because $$$\{a,b\}$$$ of the interval where $$$f(r+1)$$$ is already known, the value of $$$f(r+1)$$$ can be calculated quickly. So, the first term of $$$f(x)$$$ can be represented as below:
$$$$$$k^{r-x+1}f(r+1)=k^{r+1}f(r+1)·k^{-x}=\{k^{r+1}f(r+1),-1\}$$$$$$
Then the last term of $$$f(x)$$$, $$$\sum\limits_{i=0}^{r-x}k^i$$$ is sum of an ordinary geometric sequence. So, after applying the formula it can represented as $$$\{2,0\}+\{-k^r,-1\}$$$.
For the second term $$$\sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)$$$, it has been assumed that $$$f(2x+2i)$$$ is $$$\sum\{a,b\}$$$, so split it into the following form (the derivation process depends on $$$k^{2b+1}\neq1$$$):
$$$$$$ \!\begin{aligned} \sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)&=\sum\limits_{i=0}^{r-x}k^{i+1}\sum\limits_f\{a,b\}\\ &=\sum\limits_{i=0}^{r-x}k^{i+1}\sum\limits_fak^{b(2x+2i)}\\ &=\sum\limits_f\sum\limits_{i=0}^{r-x}k^{i+1}ak^{b(2x+2i)}\\ &=\sum\limits_f\sum\limits_{i=0}^{r-x}ak^{2bx+1}·k^{i+2bi}\\ &=\sum\limits_fak^{2bx+1}\sum\limits_{i=0}^{r-x}(k^{2b+1})^i\\ &=\sum\limits_fak^{2bx+1}\cdot\frac{k^{(2b+1)(r-x+1)}-1}{k^{2b+1}-1}\\ &=\sum\limits_f\frac{ak^{(2b+1)(n+1)+1}}{k^{2b+1}-1}\cdot k^{-x}+\frac{-ak}{k^{2b+1}-1}\cdot k^{2bx}\\ &=\sum\limits_f\{\frac{ak^{(2b+1)(n+1)+1}}{k^{2b+1}-1},-1\}+\{\frac{-ak}{k^{2b+1}-1},2b\} \end{aligned} $$$$$$
Because of the obvious combination law $$$\{a,b\}+\{c,b\}=\{a+c,b\}$$$, the number of its geometric series is linear with the number of recursions.
For $$$x\in[n,2n], f(x)=0$$$, which can be represented as $$$f(x)=\{0,0\}$$$, so this recursive rule can always be used, Until the $$$x\in[1,1]$$$ is obtained, to get the result.
The complexity varies depending on the implementation $$$\Theta(T\log^3n)$$$ or $$$\Theta(T\log^2n)$$$.