本問題を \(X=N+K+\max A\) としたとき、\(\mathrm{O}(X\log^2 X)\) で解く方法を解説します。

想定解の dp を理解しているものとして解説をします。まず、初めの \(\mathrm{mex}\) から始め、最後の \(\mathrm{mex}\) を固定しているときを数え上げます。操作全体で \(\mathrm{mex}\) が増えた回数を \(i\) 回とします。 するとこれは、dp の遷移に注目をすると \([x^{K-i}] \prod \frac{1}{1-ax}\) であることが分かります。ただし、\(a\) は操作途中で取る全ての \(\mathrm{mex}\) の値を動きます。

さて、あとはこれを全ての \(\mathrm{mex}\) について総和を取ればよいですが、これは \(f_1 + f_1f_2 + \dots + f_1 f_2 \dots f_k,\prod_{i=1}^{k} f_i\) をもって分割統治をすることで高速に求めることができます。計算量は上記の通り \(\mathrm{O}(X\log^2 X)\) です。

しかし、定数倍が非常に重いため、本問題の制約では想定解の dp よりも遅いレベルだと思われます。