問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : 👑 Kazun / テスター : 👑 potato167 👑 cologne
お気に入りにしたユーザー ProblemId : 7747 / 自分の提出
問題文最終更新日: 2022-07-06 17:33:52
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 348 Early Summer Rain (順位表) の他の問題:

Note

This problem has $2$ problem statements, G1 and G2. G1 is the statement with the story, and G2 is the statement with the story removed.

G1 and G2 describe the same problem, so choose whichever is easier for you to read.

Problem Statement G1

Cherry likes Zelkova.

Initially, Cherry's feelings for Zelkova (hereafter simply called "feelings") are $0$.

Every day, Cherry chooses $1$ action out of $(E_1+\dots+E_N)$ actions, performs it, and increases her feelings. She repeats this for some number of days.

Among the $(E_1+\dots+E_N)$ actions, $E_i$ actions increase the feelings by $i$. Note that for 1 action, there is exactly $1$ possible amount by which the feelings increase.

For each of $n=1,2, \dots, N$, answer the following question.

Let $T_n$ be the sum of the $K$-th powers of the number of days taken (the number of actions) over all "ways of acting over some number of days such that the feelings are exactly $n$ after everything is finished".

It can be proved that $T_n$ is a rational number. Find $T_n \pmod{998244353}$.

2 ways of acting are considered the same if and only if both of the following hold.

  • The numbers of days taken are equal (let this number of days be $D$).
  • For integers $i$ between $1$ and $D$, inclusive, the action taken on day $i$ is the same.

Problem Statement G2

For a sequence $S$, let $|S|$ denote the length of $S$. That is, when the sequence $S$ is written as $S=(S_1, S_2, \dots, S_l)$, we have $|S|:=l$.

You are given an integer sequence $E=(E_1, E_2, \dots, E_N)$ of length $N$.

Let $\mathcal{P}_n$ be the set of all sequences of integer pairs $P=\left((A_i, B_i)\right)_{i=1}^{|P|}$ satisfying the following.

  • $1 \leq A_i \leq N$
  • $1 \leq B_i \leq E_{A_i}$
  • $\displaystyle \sum_{i=1}^{|P|} A_i=n$

Let $T_n$ be the sum of the $K$-th powers of the lengths of the sequences of integer pairs over all elements of $\mathcal{P}_n$. It can be proved that $T_n$ is a rational number. For $n=1,2, \dots, N$, find $T_n \pmod{998244353}$.

Formally, $T_n$ is written as $\displaystyle T_n=\sum_{P \in \mathcal{P}_n} |P|^K$.

Notes

  • For a positive real number $x$ and a negative integer $k$, $x^k$ is defined as $x^k:=\dfrac{1}{x^{|k|}}$. Also, $x^0=1$.

  • Under the constraints of this problem, for each case there exist an integer $X$ that is not a multiple of $998244353$ and an integer $Y$ such that $X \times T_n =Y$.

    For these $X,Y$, there exists a unique integer $Z$ that is at least $0$ and less than $998244353$ such that $X \times Z \equiv Y \pmod{998244353}$. Using this $Z$, we define $T_n \pmod{998244353}:=Z$.

    Note that there are many possible choices of an integer $X$ that is not a multiple of $998244353$ and an integer $Y$ such that $X \times T_n =Y$, but $Z$ does not depend on the choice of $X,Y$ and is determined only by $T_n$.

Constraints

  • $1 \leq N \leq 10^5$
  • $-20 \leq K \leq 20$
  • $0 \leq E_i \lt 998244353$
  • There exists $i$ such that $E_i \neq 0$.
  • All input values are integers.

Input

$N$ $K$
$E_1$ $E_2$ $\cdots$ $E_N$

Output

Following the notes, output $T_n \pmod{998244353}$ in the order $n=1,2, \dots, N$, separated by spaces.

Do not forget the newline.

Sample

Sample 1
Input
4 -2
1 0 1 0
Output
1 748683265 443664158 436731905

(For Problem Statement G1)
There are only $2$ actions: the action that increases the feelings by $1$ ($\alpha$) and the action that increases the feelings by $3$ ($\beta$). For example, the ways of acting that make the feelings exactly $4$ are

  • $\alpha \to \alpha \to \alpha \to \alpha$
  • $\alpha \to \beta$
  • $\beta \to \alpha$
for a total of $3$ ways. The numbers of days taken are $4,2,2$, in order from the top. Therefore, we have $$T_4=4^{-2}+2^{-2}+2^{-2}=\dfrac{9}{16}$$ .

(For Problem Statement G2)
For example, $\mathcal{P}_4=\{((1,1),(1,1),(1,1),(1,1)), ((1,1),(3,1)), ((3,1),(1,1))\}$. Indeed, $1+1+1+1=1+3=3+1=4$. In this case, we have $$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}$$ .

(Common to Problem Statements G1 and G2)
Also, since $16 \times T_4=9$ and $16 \times 436731905 \equiv 9 \pmod{998244353}$, we have $T_4 \pmod{998244353}=436731905$.

Sample 2
Input
7 20
0 314159265 358979323 846264338 327950288 419716939 937510582
Output
0 314159265 358979323 662822249 266028178 11631560 288893263

(For Problem Statement G1)
It may be impossible to make the feelings exactly $n$. In this case, $T_n=0$.

(For Problem Statement G2)
$\mathcal{P}_n$ may be the empty set. In this case, $T_n=0$.

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