P6633 [ZJOI2020] Card Drawing

Bob likes drawing cards. Bob recently started playing a card-drawing game called "Zhugong Link". There are $n$ different characters in the game, numbered from $1$ to $n$. If Bob obtains $k$ cards whose numbers are consecutive, he can form the theoretically strongest team. In the current card pool, there are $m$ different cards. Each time he draws, Bob gets one card uniformly at random from the pool. If Bob draws a card he already owns, then nothing happens, which means this draw is wasted. Bob is a cautious person. He wants to know: if he keeps drawing until he has obtained $k$ cards with consecutive numbers and then stops, what is the expected number of draws needed.

The first line contains two integers $m, k$. The second line contains $m$ pairwise distinct integers $a_1, a_2, \cdots, a_m$, indicating which characters are in the card pool. In this statement, $n$ is the maximum value among $a_i$.

Output one integer in one line, representing the expected number of draws modulo $p = 998244353$. That is, if the expected value in lowest terms is $\frac{a}{b}$, you need to output an integer $c$ such that $c \times b \equiv a \pmod{p}$.

**Sample Explanation 1** If the first draw is card $2$, then the expected number of draws is $1 + \frac{3}{2}$. If the first draw is card $1$ or card $3$, then the expected number of draws is $1 + 3$. Therefore the answer is $\frac{1}{3}(1 + \frac{3}{2}) + \frac{2}{3}(1 + 3) = 3.5$. **Constraints and Notes** For the first $10\%$ of the testdata, $m \le 10$. For another $10\%$ of the testdata, $m \le 500$ and $k = m − 1$. For another $10\%$ of the testdata, $m \le 500$ and it is guaranteed that there exists exactly one theoretically strongest team. For another $10\%$ of the testdata, $m \le 500$ and it is guaranteed that any two theoretically strongest teams that can be drawn do not overlap. For the first $50\%$ of the testdata, $m \le 500$. For the first $70\%$ of the testdata, $m \le 5000$. For another $10\%$ of the testdata, $k = 5$. For another $10\%$ of the testdata, $k = 2000$. For $100\%$ of the testdata, $1 \le m \le 200000, 1 \le a_i \le 2m, 2 \le k \le m$. It is guaranteed that there exists at least one theoretically strongest team that can be drawn (i.e., $k$ cards with consecutive numbers). Translated by ChatGPT 5