P17251 Mean

An easy problem, no background.

For a multiset $S$, define one operation on $S$ as follows: - Let $\rm avg$ be the average of all elements in $S$, i.e. $\frac{\sum S}{|S|}$, where $\sum S$ is the sum of all elements in $S$, and $|S|$ is the number of elements in $S$ (duplicate elements are counted multiple times). - Let $m=\min\limits_{x \in S}|x-\mathrm{avg}|$, i.e. the minimum value of the absolute difference between an element in $S$ and $\rm avg$. - Choose an element $x$ from $S$ such that $|x-\mathrm{avg}|=m$. If multiple elements satisfy this, choose **any one** of them. - Then delete **one** $x$ from $S$, and insert **one** $\rm avg$ into $S$. For example, performing one operation on $\{2,4,1,4,6,1\}$ can yield $\{3,4,1,4,6,1\}$ or $\{2,4,1,3,6,1\}$. Note that a multiset is **unordered**. Given positive integers $n,k$ and a multiset $A=\{a_1,a_2,\cdots,a_n\}$, compute how many different multisets may be obtained after performing $k$ operations on $A$. Output the result modulo $998244353$.

The first line contains two positive integers $n,k$, separated by spaces.\ The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, separated by spaces.

Output one non-negative integer in one line, denoting the number of different multisets that may be obtained modulo $998244353$.

#### Sample 1 Explanation The following multisets may be obtained: $\{3,4,1,4,6,1\},\{2,4,1,3,6,1\}$. Note that $\{2,3,1,4,6,1\}$ is the same as $\{2,4,1,3,6,1\}$. #### Constraints It is guaranteed that $1 \le n \le 5 \times 10^5,1 \le a_i,k \le 10^9$. **This problem uses bundled testdata.** Special conditions for subtasks are as follows: | Subtask | $n$ | $k$ | $a_i$ | Score | |:-:|:-:|:-:|:-:|:-:| | 0 | $\le 5$ | $=1$ | $\le 10$ | $10$ | | 1 |^| $\le 10^9$ |^| $15$ | | 2 | $\le 5000$ | $=1$ | $\le 10^5$ | $10$ | | 3 | ^ | $\le 10^9$ |^| $15$ | | 4 | $\le 5 \times 10^5$ | $=1$ | $\le 10^9$ | $20$ | | 5 |^| $\le 10^9$ |^| $30$ | Translated by ChatGPT 5