問題一覧 > 通常問題

No.1968 Distance

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : __turtle0123__turtle0123 / テスター : shiomusubi496shiomusubi496
2 ProblemId : 8029 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-03 21:09:28

問題文

数直線上の座標 $0,1$ に人がいます。これから、ここに $N+1$ 人の人が出現します。 $1$ 人目は $0$ 以上 $1$ 以下のランダムな座標に出現し、 $2,3,\ldots,N+1$ 人目は以下の規則に従って出現します。

  • $0$ 以上 $1$ 以下の座標のうち、すでに存在する人との距離の最小値が最も大きい座標に出現する。そのようなものが複数ある場合は、ランダムに一つを選び出現する。

人と人の距離の最小値の期待値を $\bmod\ 998244353$ で求めて下さい。


  • 出力についての注記 (クリックすると展開されます)
  • この問題において出力する値は有理数であることが証明できます。また、既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ の倍数でないことも証明できます。
    ここで、 $xz \equiv y \pmod {998244353}$ を満たす整数 $z \ (0 \le z < 998244353)$ は一意に定まるので、この値を $\frac{y}{x} \bmod 998244353$ として出力してください。

    制約

    • $0 \le N \le 10^{12}$
    • 入力はすべて整数

    入力

    $N$

    出力

    答えを出力せよ。

    サンプル

    サンプル1
    入力
    0
    出力
    748683265

    期待値は $\frac{1}{4}$ です。

    サンプル2
    入力
    1
    出力
    457528662

    サンプル3
    入力
    998244353
    出力
    288988261

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。