我们先定义 关键数：加入该数后能使 $mex(S)$ 增大。在加入关键数 $x$ 前，最多只能得到小于 $x$ 的 $mex$。关键数严格递增，因此满足 $x_i+1 \le x_{i+1}$。根据 等差数列求和公式 易得关键数的个数至多为 $r=\min(\sqrt{W},K)$。

我们将所有的关键数用数组 $d$ 记录下来，例如：初始 $S=(0,2)$，则关键数为 $d[1]=1,d[2]=3$。

设 $f_{k,i,j}$ 表示第 $k$ 次操作后，已用 $i$ 个关键数，总花费为 $j$ 的方案数。转移为：

$$f_{k,i,j} = f_{k-1,i-1,j-d[i]} + \sum_{g=\max(0,\,j-d[i+1]+1)}^{j} f_{k-1,i,g}$$

初始状态：$f_{0,0,0}=1$，表示还未选择任何数，预算为 0 时只有 1 种方案。

对非关键数的转移是区间和，因此我们可以用 前缀和/双指针 来 $O(1)$ 地完成转移。这样就避免了暴力枚举。由于 DP 的第一维 $k$ 只依赖于上一层，因此可以使用 滚动数组 优化内存，将空间降为 $O(rW)$。

复杂度：时间 $O(KrW)$，空间 $O(rW)$。