\(1 \le i \le M\) に対し、操作終了後に \(A\) の要素のうち、 \(i\) 以下の値の個数の期待値が求められれば良いです。

つまり、\(i\) 以下の値の個数を \(x\) とおくことで、問題は以下のように言い換えられます。

\(0\) 以上 \(N\) 以下の整数 \(x\) が与えられる。以下の操作を \(K\) 回繰り返す時、操作終了後の \(x\) の期待値を求めよ。

・確率 \(p\) で \(x\) を \(1\) 増やす。その後、\(x \ge X\) ならば \(x\) を \(1\) 減らす。

すると、操作終了時の \(x\) を固定した場合、そのような通り数は二項係数やべき乗を使い表すことができます。

より、\(i\) を固定した場合、操作終了時の \(x\) を全探索して \(\mathrm{O}(N\log K)\) で解くことができます。

よって、二項係数の前処理などを含めこの問題を \(\mathrm{O}(MN\log K+K)\) で解くことができました。