题解

思路

固定所有新写入的数中的最大值 $x$。

做法

第一次写出 $x$ 以前，初始黑板中缺少的每个 $0,1,\ldots,x-1$ 都必须先各补一次，之后才能选出含有这些数的子集并令其 mex 为 $x$。因此第一次写出 $x$ 至少需要 $\operatorname{need}(x)=1+\#\{i\mid 0\le i<x,\ i\text{ 没有在初始黑板中出现}\}$ 次操作，而且这段最短补全过程唯一。若 $\operatorname{need}(x)\le K$，余下的 $K-\operatorname{need}(x)$ 次操作可以任意写入 $0$ 到 $x$：这些数此时都已出现，任选 $y\le x$ 时只需从黑板上选出 $0$ 到 $y-1$ 并排除 $y$，便能让 mex 等于 $y$。于是余下操作形成的多重集合数是可重复组合数 $\binom{K-\operatorname{need}(x)+x}{x}$。不同 $x$ 对应最终新增数的不同最大值，直接求和即可。

从 $x=0$ 开始扫描；初始令 $\operatorname{need}=1$，计入当前组合数后，若初始黑板中没有 $x$，就将 $\operatorname{need}$ 加一。可行的 $x$ 不会超过 $N+K-1$。

复杂度

预处理到 $N+K$ 的阶乘与逆阶乘即可在常数时间求每个组合数，总时间复杂度为 $O(N+K+\log 998244353)$，空间复杂度为 $O(N+K)$。