The problem is solved if, for each \(1 \le i \le M\), we find the expected value of the number of values in \(A\) not greater than \(i\) after the operations.

That is, the problem can be rephrased into the following.

You are given an integer $x$ between $0$ and $N$. Find the expected value of $x$ after repeating the following operation $K$ times.

・Increase $x$ by $1$ with probability $p$. Then, if $x \ge X$, decrease $x$ by $1$.

Notice that \(|x-(X-1)|\) will decrease monotonically.

Hence, if we fix the final value of \(x\), the probability of getting it can be represented using binomial coefficients and powers.

Thus, for a fixed \(i\), the sought value can be found in \(\mathrm{O}(N\log K)\) time.

Therefore, we have solved the whole problem in \(\mathrm{O}(MN\log K+K)\) time, including pre-computations of binomial coefficients and such.