問題一覧 > 通常問題

No.1357 Nada junior high school entrance examination 3rd day

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 4
作問者 : PCTprobabilityPCTprobability / テスター : KoDKoD maguromaguro
0 ProblemId : 5753 / 出題時の順位表
問題文最終更新日: 2021-02-18 17:18:40

問題文

本来灘中入試は2日間ですが、どうやら2021年は隠れた3日目があったみたいです。その問題を解いてください。

正整数 $N,M$ に対して、以下のように関数 $f(N,M)$ を定めます。 表が $Z$ の確率で出るコインを用意し、以下のゲームを $N$ 回続けます。最初は $Y=1$、$Z = 1$ です。 $i \,\, (1 \leq i \leq N)$ 回目のゲームでは以下のような操作をします。

  • コインを $1$ 回投げ、表が出たならば $Y×(-1)^{i+1}$ 点を得る。
  • $Z$ を $ \frac{i^{M-1}}{(i+1)^M}×Z$ で置き換える。
  • $Y$ を $(N-i)×Y$ で置き換える。
最終的に得られる点の総和の期待値を $f(N,M)$ とします。 正整数 $K$ が与えられるので、\( \displaystyle \sum_{a=1}^{K} \displaystyle \sum_{b=1}^{∞} \frac{f(b,2a-1)}{b} \) を求めてください。 ここで、この値は有理数列 $c_0,c_1,...,c_{2K}$ によって、\( \displaystyle \sum_{i=0}^{2K}c_iπ^i \) と一意に表すことが出来ることが証明できます。 これらの有理数列 $c_0,c_1,...,c_{2K}$ を $ \bmod 998244353$ で空白区切りで出力してください。

有理数を $ \bmod 998244353$ で出力とは、互いに素である整数 $P$ と $998244353$ で割り切れない正整数 $Q$ によって $c_i=\frac{P}{Q}$ (既約分数)と表せることが保証されるので、 $P \equiv Q×R \bmod 998244353$ となる唯一の $0$ 以上 $998244353$ 未満の正整数 $R$ を出力する、ということです。

入力

$K$

  • 入力は全て正整数である。
  • $1 \le K \le 5×10^4$

出力

\( \displaystyle \sum_{a=1}^{K} \displaystyle \sum_{b=1}^{∞} \frac{f(b,2a-1)}{b} \) を求めてください。 ここで、この値は有理数列 $c_0,c_1,...,c_{2K}$ によって、\( \displaystyle \sum_{i=0}^{2K}c_iπ^i \) と一意に表すことが出来ることが証明できます。 これらの有理数列 $c_0,c_1,...,c_{2K}$ を $ \bmod 998244353$ で空白区切りで出力してください。

サンプル

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

\( \displaystyle \sum_{a=1}^{1} \displaystyle \sum_{b=1}^{∞} \frac{f(b,2a-1)}{b} \)$= \frac{π^2}{6}$ です。

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