No.1985 [Cherry 4th Tune] Early Summer Rain
タグ : / 解いたユーザー数 10
作問者 : 👑
Kazun
/ テスター :
👑 
potato167
👑 注意
この問題は G1, G2 の $2$ つの問題文がある. G1 はストーリを入れた問題文, G2 はストーリーを排除した問題文である.
G1, G2 は同じ問題を表しているので, 各自が読みやすい方を選ぶこと.
問題文 G1
チェリーちゃんはゼルコバ君のことが好きである.
最初, チェリーちゃんのゼルコバ君に対する想い (以降では単に想いという) は $0$ である.
チェリーちゃんは毎日 $(E_1+\dots+E_N)$ 個ある行動から $1$ つを選び, それを実行し, 想いを増やす. これを何日か繰り返す.
$(E_1+\dots+E_N)$ 個の行動のうち, 想いが $i$ 増えるような行動は $E_i$ 個である. なお, 1つの行動において, 増える想いの候補はただ $1$ つである.
このとき, $n=1,2, \dots, N$ それぞれに対して, 以下の問に答えよ.
「全てを終えた後に想いがちょうど $n$ になるような何日間かの行動の方法」全てにおける所要日数 (行動の回数) の $K$ 乗和 を $T_n$ とする.
$T_n$ は有理数であることが証明できる. このとき, $T_n \pmod{998244353}$ を求めよ.
2つの行動の仕方において, 以下を共に満たすとき, そして, このときに限り, この行動の仕方は同じであるとする.
- 所要日数が等しい (その所要日数を $D$ とする).
- $1$ 以上 $D$ 以下の整数 $i$ に対して, $i$ 日目にした行動が同じである.
問題文 G2
列 $S$ に対して, $|S|$ で $S$ の長さを表すとする. つまり, 列 $S$ を $S=(S_1, S_2, \dots, S_l)$ としたとき, $|S|:=l$ である.
長さが $N$ である整数列 $E=(E_1, E_2, \dots, E_N)$ が与えられる.
$\mathcal{P}_n$ を以下を満たす整数対の列 $P=\left((A_i, B_i)\right)_{i=1}^{|P|}$ 全体の集合とする.
- $1 \leq A_i \leq N$
- $1 \leq B_i \leq E_{A_i}$
- $\displaystyle \sum_{i=1}^{|P|} A_i=n$
$\mathcal{P}_n$ の元全てに渡る整数対の列の長さの $K$ 乗和を $T_n$ としたとき $T_n$ は有理数となることが証明できるが, $n=1,2, \dots, N$ に対して $T_n \pmod{998244353}$ を求めよ.
なお, $T_n$ を厳密に記述すると, $\displaystyle T_n=\sum_{P \in \mathcal{P}_n} |P|^K$ である.
注記
正の実数 $x$ と負の整数 $k$ に対して, $x^k$ は $x^k:=\dfrac{1}{x^{|k|}}$ と定義される. また, $x^0=1$ である.
この問題の制約下において, それぞれ $X \times T_n =Y$ となる $998244353$ の倍数ではない整数 $X$ と, 整数 $Y$ が存在する.
この $X,Y$ に対して, $X \times Z \equiv Y \pmod{998244353}$ となる $0$ 以上 $998244353$ 未満の整数 $Z$ が唯一存在するので, この $Z$ を用いて, $T_n \pmod{998244353}:=Z$ とする.
なお, $X \times T_n =Y$ となる $998244353$ の倍数ではない整数 $X$ と, 整数 $Y$ は数多に考えられるが, $Z$ は $X,Y$ の取り方によらず, $T_n$ にのみによって決まる.
制約
- $1 \leq N \leq 10^5$
- $-20 \leq K \leq 20$
- $0 \leq E_i \lt 998244353$
- $E_i \neq 0$ となる $i$ が存在する.
- 入力は全て整数である.
入力
$N$ $K$ $E_1$ $E_2$ $\cdots$ $E_N$
出力
注記に従い, $T_n \pmod{998244353}$ を $n=1,2, \dots, N$ の順に空白区切りで出力せよ.
改行を忘れないこと.
サンプル
サンプル1
入力
4 -2 1 0 1 0
出力
1 748683265 443664158 436731905
(問題文 G1 用)
想いを $1$ 増やす行動 ($\alpha$) と, 想いを $3$ 増やす行動 ($\beta$) の $2$ つだけがある. 例えば, 想いをちょうど $4$ にする行動の仕方は
- $\alpha \to \alpha \to \alpha \to \alpha$
- $\alpha \to \beta$
- $\beta \to \alpha$
(問題文 G2 用)
例えば, $\mathcal{P}_4=\{((1,1),(1,1),(1,1),(1,1)), ((1,1),(3,1)), ((3,1),(1,1))\}$ である. 実際, $1+1+1+1=1+3=3+1=4$ である. このとき,
$$T_4=|((1,1),(1,1),(1,1),(1,1))|^{-2}+|((1,1),(3,1))|^{-2}+|((3,1),(1,1))|^{-2}=4^{-2}+2^{-2}+2^{-2}=\dfrac{9}{16}$$
である.
(問題文 G1, G2 共通)
また, $16 \times T_4=9$ 及び, $16 \times 436731905 \equiv 9 \pmod{998244353}$ であるから, $T_4 \pmod{998244353}=436731905$ である.
サンプル2
入力
7 20 0 314159265 358979323 846264338 327950288 419716939 937510582
出力
0 314159265 358979323 662822249 266028178 11631560 288893263
(問題文 G1 用)
想いをちょうど $n$ にすることができない場合がある. この場合, $T_n=0$ である.
(問題文 G2 用)
$\mathcal{P}_n$ が空集合になる可能性がある. この場合, $T_n=0$ である.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。