N≤35N\le 35N≤35，爆搜肯定会超时，所以我们使用 爆搜\sqrt{爆搜}爆搜 算法。 我们把数据拆成两半，用两个集合记录下这两半所有的状态，然后去贪心匹配。 假设第一个集合内有一个状态为 KKK，模数为 XXX。那么如果想让和最大，那么就得找第二个集合中最后一个小于 X−KX-KX−K 的数。 代码如下： 设 M=2NM=2^NM=2N，则时间复杂度为 O(Mlog⁡M)O(\sqrt M\log M)O(M logM)。

折半搜索板子题。 发现应当使用搜索，但是爆搜会T，而且刚好可以通过 O(2n/2)O(2^{n/2})O(2n/2) 的数据，容易联想到折半搜索。 AC Code: