No.1968 Distance
レベル :
/ AI推定難易度 : 2600
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 :
ytqm3
/ テスター :
shiomusubi496
タグ : / 解いたユーザー数 23
作問者 :
shiomusubi496
問題文最終更新日: 2023-06-03 13:58:22
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 346
(順位表)
の他の問題:
Problem Statement
There are people at coordinates $0,1$ on a number line. From now on, $N+1$ more people will appear here. The $1$-st person appears at a random coordinate between $0$ and $1$, inclusive, and the $2,3,\ldots,N+1$-th people appear according to the following rule.
Among the coordinates between $0$ and $1$, inclusive, the person appears at the coordinate that maximizes the minimum distance to the people already present. If there are multiple such coordinates, one of them is chosen at random and the person appears there.
Find the expected value of the minimum distance between people, modulo $\bmod\ 998244353$.
Note on the output (click to expand)
It can be proved that the value to be output in this problem is a rational number. It can also be proved that when it is expressed as an irreducible fraction $\frac{y}{x}$, $x$ is not a multiple of $998244353$.Here, an integer $z \ (0 \le z < 998244353)$ satisfying $xz \equiv y \pmod {998244353}$ is uniquely determined, so output this value as $\frac{y}{x} \bmod 998244353$.
Constraints
- $0 \le N \le 10^{12}$
- All inputs are integers.
Input
$N$
Output
Output the answer.
Sample
Sample 1
Input
0
Output
748683265
The expected value is $\frac{1}{4}$.
Sample 2
Input
1
Output
457528662
Sample 3
Input
998244353
Output
288988261
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。