No.2586 Yet Another Sugoroku Problem
タグ : / 解いたユーザー数 42
作問者 :
Shirotsume
/ テスター :
kaichou243
問題文
正整数 $N$ が入力に与えられます。正整数 $M$ が与えられたときの以下の問題に対する答えを $f(M)$ とおきます。
変数 $X$ があります。はじめ、$X = 0$ で初期化されています。
Shirotsume くんは $N$ 面サイコロを持っています。$N$ 面サイコロを振ると、$1$ 以上 $N$ 以下の目が同様に確からしい確率で出ます。
これから、$N$ 面サイコロを振り出た目と等しい数だけ $X$ の値を増やす操作を繰り返します。$X$ の値が $M$ 以上となったとき、操作を終了します。
操作を行う回数の期待値を求めてください。
極限 $\displaystyle \lim_{M \rightarrow \infty} \frac{f(M)}{M}$ が存在することが証明できます。この値を $\bmod 998244353$ で求めてください。
$\bmod 998244353$ とは（クリックで展開）
この問題で求める答えは必ず有理数です。また、この問題の制約下で答えを既約分数 $\frac{P}{Q}$ で表した時、 $Q$ が $998244353$ で割り切れないことが示せます。
このとき $P \equiv QR (\bmod 998244353)$ を満たす $0$ 以上 $998244353$ 未満の整数 $R$ が一意に定まります。この $R$ を出力してください。
制約
- $N$ は整数
- $1 \leq N \leq 2 \times 10^5$
入力
入力は標準入力から以下の形式で与えられる。
$N$
出力
答えを $\bmod 998244353$ で出力せよ。
サンプル
サンプル1
入力
1
出力
1
サイコロは $1$ の目しか出ないので、 $f(M) = M$ です。よって、$\displaystyle \lim_{M \rightarrow \infty} \frac{f(M)}{M} = 1$ となるので、 $1$ を出力してください。
サンプル2
入力
100
出力
780804989
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。