No.1968 Distance
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 :
ytqm3
/ テスター :
shiomusubi496
タグ : / 解いたユーザー数 23
作問者 :
ytqm3
/ テスター :
shiomusubi496
問題文最終更新日: 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$ として出力してください。
制約
- $0 \le N \le 10^{12}$
- 入力はすべて整数
入力
$N$
出力
答えを出力せよ。
サンプル
サンプル1
入力
0
出力
748683265
期待値は $\frac{1}{4}$ です。
サンプル2
入力
1
出力
457528662
サンプル3
入力
998244353
出力
288988261
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。