問題一覧 > 通常問題

No.1985 [Cherry 4th Tune] Early Summer Rain

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 👑 KazunKazun / テスター : colognecologne potato167potato167
0 ProblemId : 7747 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-17 23:05:08

注意

この問題は 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$
の $3$ 個である. 所要日数は上から順に $4,2,2$ である. このことから, $$T_4=4^{-2}+2^{-2}+2^{-2}=\dfrac{9}{16}$$ である.

(問題文 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もしくは右上の雲マークをクリックしてアカウントを作成してください。