No.2391 SAN 値チェック
タグ : / 解いたユーザー数 32
作問者 : 👑
PCTprobability
/ テスター :
cleantted
👑 
tatyam
👑 
Mizar
👑 
amentorimaru
問題文
正整数 $N$ が与えられます。
あなたは実数 $X$ を持っています。はじめ、$X=N$ となっています。あなたは以下の操作を $X$ が $0$ 以上である間繰り返します。
- $0$ 以上 $1$ 以下の実数を $1$ 個一様ランダムに選んで $X$ から引く。
このとき操作回数の期待値を $A$ と置くと、長さ $N+1$ の有理数列 $(a_0,a_1,\dots,a_N)$ であって $A = \sum_{i=0}^{N} a_i e^i$ を満たすものが一意に存在します。ただし、$e$ はネイピア数です。
$i = 0,1,\dots,N$ に対して、$a_i \bmod 998244353$ を求めてください。
有理数 $\bmod\ 998244353$ の定義
$a_i(0 \le i \le N)$ は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表した時、$Q \neq 0 \pmod{998244353}$ となることも証明できます。よって、$R \times Q = P \pmod{998244353},0 \le R < 998244353$ を満たす整数 $R$ が一意に定まります。この $R$ を答えてください。
入力
$N$
- $1 \le N \le 2 \times 10^5$
- $N$ は整数である。
出力
$N+1$ 行出力せよ。$i(1 \le i \le N+1)$ 行目には、$a_{i-1} \bmod 998244353$ を出力せよ。
サンプル
サンプル1
入力
1
出力
0 1
操作回数の期待値は $e$ です。
サンプル2
入力
2
出力
0 998244352 1
操作回数の期待値は $e^2 - e$ です。
サンプル3
入力
3
出力
0 499122177 998244351 1
操作回数の期待値は $e^3 - 2e^2 + \frac{e}{2}$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。