問題一覧 > 通常問題

No.2391 SAN 値チェック

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : PCTprobability / テスター : cleantted tatyam 👑 Mizar 👑 amentorimaru
7 ProblemId : 9727 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-21 23:08:29

問題文

正整数 NN が与えられます。

あなたは実数 XX を持っています。はじめ、X=NX=N となっています。あなたは以下の操作を XX が 00 以上である間繰り返します。

  • 00 以上 11 以下の実数を 11 個一様ランダムに選んで XX から引く。

このとき操作回数の期待値を AA と置くと、長さ N+1N+1 の有理数列 (a0,a1,…,aN)(a_0,a_1,\dots,a_N) であって A=∑i=0NaieiA = \sum_{i=0}^{N} a_i e^i を満たすものが一意に存在します。ただし、ee はネイピア数です。

i=0,1,…,Ni = 0,1,\dots,N に対して、ai mod 998244353a_i \bmod 998244353 を求めてください。

有理数  mod  998244353\bmod\ 998244353 の定義

ai(0≤i≤N)a_i(0 \le i \le N) は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 PQ\frac{P}{Q} で表した時、Q≠0(mod998244353)Q \neq 0 \pmod{998244353} となることも証明できます。よって、R×Q=P(mod998244353),0≤R<998244353R \times Q = P \pmod{998244353},0 \le R < 998244353 を満たす整数 RR が一意に定まります。この RR を答えてください。

入力

NN

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • NN は整数である。

出力

N+1N+1 行出力せよ。i(1≤i≤N+1)i(1 \le i \le N+1) 行目には、ai−1 mod 998244353a_{i-1} \bmod 998244353 を出力せよ。

サンプル

サンプル1
入力
1
出力
0
1

操作回数の期待値は ee です。

サンプル2
入力
2
出力
0
998244352
1

操作回数の期待値は e2−ee^2 - e です。

サンプル3
入力
3
出力
0
499122177
998244351
1

操作回数の期待値は e3−2e2+e2e^3 - 2e^2 + \frac{e}{2} です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。