P10328 [UESTCPC 2024] Card Game

Li Hua has a deck of cards. Each card has three attributes: color, number, and value. The color of each card can be represented by an integer in $[1,n]$, and similarly, each card also has a number that is an integer in $[1,n]$. Based on different numbers and colors, these cards are divided into $n^2$ types. For convenience, define that the type ID of a card with color $x$ and number $y$ is $(x-1)\times n+y$. In the deck, there are $a_i$ cards of type $i$, and the value of each card of type $i$ is $b_i$. At the beginning, Li Hua has an empty hand and an initial score of $0$. Li Hua will play for $k$ rounds. At the start of each round, Li Hua **randomly** draws one card from the remaining cards in the deck, and each remaining card has an equal probability of being drawn. Next, if the hand contains any card whose number **or** color is the same as the drawn card, then Li Hua returns **all** cards in the hand that satisfy the above condition, together with the drawn card, back into the deck. Otherwise, the drawn card is placed into the hand. After each round ends, Li Hua's score increases by the sum of the values of all cards currently in the hand. Please compute the expected total score after $k$ rounds, and output it modulo $998244353$.

The first line contains two positive integers $n,k$ $(2\le n\le 4, 1\le k\le 10^9)$, representing the number of colors and numbers, and the number of rounds. The second line contains $n^2$ integers $a_i$ $(0\le a_i

Output one integer on one line, representing the expected total score after $k$ rounds.

For the first sample, the correspondence between the final score and its probability is as follows. | Score | $1$ | $2$ | $3$ | $4$ | $5$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | Probability | $\frac 12$ | $\frac 16$ | $\frac 16$ | $\frac 1{12}$ | $\frac 1{12}$ | The expected score is $\frac{25}{12}$. For the second sample, the expected score is $\frac{5041}{810}$. Translated by ChatGPT 5