サノスソート I - Problem

サノスは従来のソートアルゴリズムが好きではありません。

長さ $m$ の数列 $a_1, a_2, \dots, a_m$ に対して、「サノスソート」操作を次のように定義します：

現在の数列がすでに狭義単調増加、すなわち $a_1 < a_2 < \dots < a_m$ を満たすなら、アルゴリズムは直ちに終了します。
そうでなければ、現在の数列の $m$ 個の位置からちょうど $\lfloor m / 2 \rfloor$ 個の位置を一様ランダムに選んで削除します。残りの要素の相対的な順序を保ち、残った数列に対して同じ処理を続けます。

上の削除操作における $m$ は、初期の長さではなく、現在の数列の長さを表します。つまり、あるラウンドの開始時点で要素が $m$ 個残っており、数列がまだソートされていないなら、そのラウンドでは $\lfloor m / 2 \rfloor$ 個の要素をランダムに削除します。

まず長さ $N$ の順列 $p_1, p_2, \dots, p_N$ を一様ランダムに生成し、その順列にサノスソートを行います。

最後に残る要素数を $X$ とします。$\mathbb{E}[X]$ を求め、答えを $998244353$ で割った余りを出力してください。

入力は一行だけで、初期の順列の長さを表す整数 $N$ $(1 \le N \le 10^6)$ が与えられます。

$\mathbb{E}[X]$ を $998244353$ で割った余りを表す整数を一行に出力してください。

より形式的には、$\mathbb{E}[X]$ を既約分数で表したものが $\dfrac{P}{Q}$ であれば、$P \cdot Q^{-1} \bmod 998244353$ を出力してください。ここで $Q^{-1}$ は、法 $998244353$ における $Q$ の乗法逆元です。

この問題の制約内では、上記の逆元が必ず存在することを証明できます。

499122178

83187031

長さ $2$ の順列は二種類だけです：

$[1, 2]$：数列はすでにソートされているので、最後に残る要素数は $2$ です。
$[2, 1]$：数列はソートされていないので、$1$ 個の要素をランダムに削除する必要があります。どちらを削除しても、残る数列の長さは $1$ で必ずソート済みとなるため、最後に残る要素数は $1$ です。

したがって、$\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$ です。

法 $998244353$ では、$\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$

QOJ.ac