No.1985 [Cherry 4th Tune] 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 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun