No.1968 Distance

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 :

ytqm3 / テスター :

shiomusubi496

4 ProblemId : 8029 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-06-03 13:58:22

数直線上の座標 $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

として出力してください。

$N$

答えを出力せよ。

748683265

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

457528662

998244353

288988261

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