No.2586 Yet Another Sugoroku Problem
タグ : / 解いたユーザー数 44
作問者 :
Shirotsume
/ テスター :
kaichou243
Problem Statement
A positive integer $N$ is given as input. For a given positive integer $M$, let $f(M)$ denote the answer to the following problem.
There is a variable $X$. Initially, it is set to $X = 0$.
Shirotsume has an $N$-sided die. When the $N$-sided die is rolled, it shows a value between $1$ and $N$, inclusive, with equal probability.
He repeats the operation of rolling the $N$-sided die and increasing the value of $X$ by the number shown. The operations end when the value of $X$ becomes at least $M$.
Find the expected number of operations performed.
It can be proved that the limit $\displaystyle \lim_{M \rightarrow \infty} \frac{f(M)}{M}$ exists. Find this value $\bmod 998244353$.
What $\bmod 998244353$ means (click to expand)
The answer to this problem is always a rational number. It can also be shown that, under the constraints of this problem, when the answer is expressed as an irreducible fraction $\frac{P}{Q}$, $Q$ is not divisible by $998244353$.
Then, there is a unique integer $R$ that is at least $0$ and less than $998244353$ satisfying $P \equiv QR (\bmod 998244353)$. Print this $R$.
Constraints
- $N$ is an integer
- $1 \leq N \leq 2 \times 10^5$
Input
The input is given from standard input in the following format.
$N$
Output
Print the answer $\bmod 998244353$.
Sample
Sample 1
Input
1
Output
1
The die only ever shows $1$, so $f(M) = M$. Hence, $\displaystyle \lim_{M \rightarrow \infty} \frac{f(M)}{M} = 1$, so print $1$.
Sample 2
Input
100
Output
780804989
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。