P5577 [CmdOI2019] Computing Power Training

Recently, the problem setter happily learned how to solve a quadratic equation in one variable. At night in the dorm, the problem setter dreamed of a country that uses base $k$. When in Rome, do as the Romans do, so the problem setter also used base $k$ there. Of course, people in that country also know mathematics, so the problem setter, who still could not solve a quadratic equation in one variable, did not escape computing power training.

The problem setter wrote down $n$ base-$k$ natural numbers on a slip of paper. Because he is lazy, these numbers will not have too many digits, and none of them exceeds $m$ digits. To train computing power, each time he will **randomly pick a subsequence** (it is allowed to pick none), and then add all the chosen numbers together. He also felt carrying was too troublesome, so he simply规定 that **addition is done without carry**. After computing a few times, he suddenly wanted to know how many ways he can obtain each number, but he is too weak and cannot compute it. After thinking hard, he was suddenly pulled out of the dream by the wake-up bell. He found this problem interesting, so he had to ask you, who can crush countless algebra problems with one hand, to help compute it. **Formal statement**: For a sequence $A$, define its weight $W(A)$ as the sum of the elements in $A$ using base-$k$ addition without carry. Given $m$, $k$, and a sequence $S$ of length $n$. It is guaranteed that $S\subseteq [0,k^m)∩Z$. For $t=0,1,2,...,k^m-1$, compute the value of: $${\rm Ans}[t]=\sum\limits_{\text{R is a subsequence of S}}\big[W(R)=t\big]$$ Note: From the correct statement, we can infer that $\sum\limits_{t=0}^{k^m-1}{\rm Ans}[t]=2^n$.

The first line contains three integers $n,k,m$, with the meaning described in the statement. The second line contains $n$ integers separated by spaces, representing the numbers on the slip of paper. (**Note**: the numbers on the slip of paper are all base-$k$ numbers.)

There are $k^m$ lines. On the $i$-th line, output the number of ways to obtain the number $i-1$. Output the answer modulo $998244353$.

### Sample Explanation For Sample #1, there are $2^3=8$ ways to choose a subsequence: 1. Choose nothing, the sum is $0$. 2. Choose $1$, the sum is $1$. 3. Choose $2$, the sum is $2$. 4. Choose $3$, the sum is $3$. 5. Choose $1+2$, the sum is $3$. 6. Choose $1+3$, the sum is $4$. 7. Choose $2+3$, the sum is $0$ (since it is base $5$, it should become $10$, but without carry it becomes only $0$). 8. Choose $1+2+3$, the sum is $1$. In summary, the numbers of ways to obtain `0,1,2,3,4` are `2,2,1,2,1`, respectively. ### Constraints and Conventions | Test Point ID | 　n　 | 　k　 | 　m　 | Total Score | | :--: | :--: | :--: | :--: | :--: | | #1 | $20$ | $5$ | $4$ | $5$ | | #2 | $1000$ | $5$ | $4$ | $5$ | | #3~4 | $10^6$ | $5$ | $5$ | $10$ | | #5 | $10^6$ | $5$ | $6$ | $10$ | | #6~7 | $10^6$ | $5$ | $7$ | $20$ | | #8 | $20$ | $6$ | $4$ | $5$ | | #9 | $1000$ | $6$ | $4$ | $5$ | | #10~11 | $10^6$ | $6$ | $4$ | $10$ | | #12~14 | $10^6$ | $6$ | $6$ | $30$ | Translated by ChatGPT 5