CSP-S 打炸了，然后晚上又打炸了，有点破防。

设 $$$f_{i,j}$$$ 表示 $$$k=i$$$，$$$a$$$ 序列中我已经选了前 $$$j$$$ 个。初始 $$$f_{1,0}=0$$$，其余为极大值。每次可以令 $$$k$$$ 加一，于是 $$$f_{i+1,j}=\min(f{i+1,j},f_{i,j})$$$。来考虑同层之间的转移，可以二分出极长合法段，设其长度为 $$$len$$$，只对 $$$f_{i,j+len}$$$ 转移显然是答案不劣的，但这样会导致方案统计少。考虑如下情况，$a$ 序列为 10 1 1，$b$ 序列为 11，我第一次不一定非要取出 $$$len=2$$$ 个才最优，显然也可以只取出 $$$1$$$ 个。因此，为了完成 D2，我们需要对 $$$[j+1,j+len]$$$ 都更新答案。我们可以使用 set 来维护这一过程。

具体地，set 维护当前所有合法转移及其方案数，每个 $$$f_{i,j}$$$ 的贡献在 $$$j+len+1$$$ 处消失，我们可以在那里删去它的贡献。注意到我们要合并 set 中的相同代价的转移的方案数，因此可以使用 mutable 关键字来完成。每次从 set 中取出最小值进行转移。注意，我们不能认为一个转移的方案数在模意义下为 $$$0$$$ 时等价于这个转移失效，应该额外记录，否则你过不了 pretest，应该 WA on 29。

下面这份代码中的注释是不用 set 维护而暴力转移的办法，可以配合理解。

Code