折半搜索：把另一半变成一次查询

折半搜索（Meet-in-the-middle，也叫折半枚举）适合处理这样一类问题：完整方案太多，枚举不完，但只看一半的选择，规模还可以接受。

它的关键动作是：把完整选择拆成两半，各自枚举；固定一半以后，向另一半查询需要的搭档。

学会“从中间切开”只走了一步。真正决定能不能加速的，是两半保存什么信息，以及能不能快速找到搭档。

本文默认你已经会“每个元素选或不选”的子集枚举，了解排序与二分查找。需要回顾时，可以先看 子集枚举 和 二分查找。

一、 数据范围的暗号：为什么偏偏是三四十？

考虑一个最朴素的选择问题：给出 $n$ 个数，每个数可以选，也可以不选。完整选择共有 $2^n$ 种。

先别急着记算法名，看看哪些参数允许我们付出代价。

这里的 $35$ 很有意思：它远没有大到可以完全放弃指数算法，却刚好超过了直接枚举子集的舒适范围。

把指数切成两部分，数量就变了：

完整选择有约 $3.4\times 10^{10}$ 种；左右两半分别枚举，却只需生成约 $39$ 万个状态。

“三四十”不是硬性门槛。每个变量若有三种选择，直接搜索是 $3^n$，折半后的规模也要按 $3^{n/2}$ 来算；每个变量有上百种取值时，即使变量只有六个，也可能需要折半。

同样，几百万个状态能否接受，要看状态大小、排序和查询成本、时限与语言。不能仅凭状态数承诺固定的毫秒数。

二、 从暴力走到折半：省下的究竟是什么？

1. 一个完整方案，恰好对应一对半边方案

先用一个没有取模的模型：从若干正整数中选一些，让总和不超过 $T$，并且尽量大。

把数组分成互不重叠的左右两半。任意子集 $S$ 都可以唯一写成：

其中 $S_L$ 只选左半的元素，$S_R$ 只选右半的元素。反过来，任意一对左右选择也唯一确定一个完整子集。

这说明切开不会漏掉答案；做计数时，也不会因为切分本身重复计算。后续只需保证查询过程正确处理每一对合法选择。

2. 两半枚举出来，仍然不能两重循环

设左半的所有子集和组成数组 $A$，右半组成数组 $B$。若枚举所有 $(u,v)$：

只切开再两两尝试，复杂度没有下降。

现在固定左半的和 $u$。右半需要回答的问题变成：

这已经是一个有序数组上的前驱查询。将 $B$ 排序，每个 $u$ 只做一次二分，就不必逐个检查右半的所有选择。

折半搜索省掉的，正是原来逐对检查搭档的工作。

3. 一次手算，看到“查询”的感觉

设 $T=10$，数组切成 $[3,8]$ 和 $[4,7]$：

固定左半以后，右半的任务就很具体了：

这里允许直接跳过 $u>T$，是因为这个模型中的数都为正，右半无法把超出的总和降回来。换成有负数的模型，这个判断就不能照搬。

你可以把右半理解成提前整理好的一张表：左半报出“我还剩多少额度”，右半立即回答“我最多能补多少”。“双向奔赴”是一个好记的画面，但这张表怎样回答查询，才是需要真正推导的部分。

三、 学折半搜索，要形成哪几种感觉？

1. 切的是决策，保存的是摘要

枚举时，我们走过的是具体选择；合并时，通常只需要它的某些属性。

这里有一个判断标准：如果两种半边选择保存的状态相同，它们面对任意另一半时，是否真的表现相同？

在只关心子集和的最值题中，相同的和可以合并。若题目还限制选取个数，仅存总和就丢失了信息，必须再保存个数。若题目要输出具体方案，还需要记录来源，例如子集掩码。

2. 半边的最优，未必拼成整体最优

不要把每半边都压成一个“最大值”。以模 $10$ 为例，左半固定余数 $8$，右半有余数 $1$ 和 $7$：

右半单独更大的 $7$，反而是更差的搭档。必须保留足够多的候选，让左半根据自己的需要来查询。

真正安全的压缩，需要证明被删除的状态不可能带来更好的答案。

3. 瓶颈从“枚举”转到了“合并”

同样是折半，合并方式可能完全不同。判等要找精确补数，容量限制要找前驱，计数要保留重数，多属性最优还要处理状态之间的优劣关系。

因此，遇到一道新题时，最值得写在草稿纸上的一句话是：

固定左半状态后，右半需要回答什么查询？

只要这句话能写得具体，下一步往往就是选哈希表、排序二分、双指针，或者更合适的数据结构。

4. 折半与剪枝，可以配合，但省事的原因不同

剪枝是在搜索过程中证明某些分支不必再走；折半则是重新组织完整选择的配对方式。即使没有多少分支可以剪，折半也可能依靠快速合并获得稳定的规模缩减。

对于正重量的容量问题，两者可以配合：生成半边状态时，超过容量便停止扩展。但在取模最大值问题中，当前原始和超过模数，并不表示后续选择无用，不能套用这样的剪枝。

四、 用 CF 888E 走一遍：从两类取模到一次二分

1. 为什么适合作为入门例题？

codeforces 888E: Maximum Subsequence

题意是从 $n$ 个数中任选一个子序列，允许为空，使元素和模 $m$ 的余数最大。约束为 $n\le35$、$m\le10^9$。原题面

这道题适合学习折半搜索：每个数只有选或不选，半边只需要保存一个余数，合并只依赖排序和二分。它同时提醒我们：看出可以折半以后，还必须处理取模带来的非单调性。

2. 为什么半边只需保存余数？

设两半原始子集和分别为 $x,y$，则：

因此，只保存余数不会影响任意配对的结果。令左右半边的余数数组分别为 $A,B$，目标变成：

注意：这里的“数组”可能包含重复余数；每个半边的空集都要生成一个 $0$。

3. 取模只会发生两种情况

由于 $0\le u,v<m$，所以 $0\le u+v<2m$，最多减去一次 $m$。

对于第一种情况，将 $B$ 排序，调用 lower_bound(B.begin(), B.end(), m-u)。它指向第一个大于等于 $m-u$ 的位置，前一个位置就是所求。

对于第二种情况，若存在回绕候选，那么 $B$ 的最大值也必然在回绕区间中，所以取最大值即可；若连最大值都不能回绕，则这一类不存在。

到这里，分别检查两类候选，已经可以得到正确算法。

4. 再观察一步：为什么可以舍弃回绕？

对于任意回绕的配对，有：

最后一步来自 $v<m$。而右半的空集提供了余数 $0$，可以改选 $(u,0)$，得到合法结果 $u$。

也就是说，每一对回绕方案，都存在一对更好的不回绕方案。 因此求全局最大值时，完全可以舍弃回绕候选，每个 $u$ 只做一次前驱查询。

这个结论用到了“允许右半不选任何数”。若题目增加了两半必须非空、必须选固定个数等条件，就必须重新检查替代方案是否合法。

5. 沿用刚才的四个数，看一次取模合并

现在令 $m=10$，仍将 $[3,8,4,7]$ 切成 $[3,8]$ 和 $[4,7]$。子集和取模以后，两半余数排序为：

最后一行对应选取 $8,4,7$：总和为 $19$，余数为 $9$。右半的余数 $1$ 来自 $4+7$，并不要求它本身是数组中的一个元素。

当 $u=3$ 时，阈值恰好是 $7$。此时不能选 $v=7$，因为相加等于 $m$，取模后会变成 $0$。这也解释了为什么这里使用 lower_bound 的前驱。

6. 生成、整理、查询：一份完整实现

DFS 的每一层只决定当前数选不选，到半边末尾时记录余数。若一半有 $k$ 个数，叶子有 $2^k$ 个，整棵递归树的节点数也是 $O(2^k)$；不需要对每个子集重新扫一遍所有元素求和。

下面的代码只排序右半。重复余数保留也不影响最值，去重是可选优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int n;
long long m;
vector<long long> a;

// 枚举下标区间 [pos, end) 的所有选择；sum 始终是模 m 的余数。
void dfs(int pos, int end, long long sum, vector<long long>& result) {
    if (pos == end) {
        result.push_back(sum);
        return;
    }

    dfs(pos + 1, end, sum, result);
    dfs(pos + 1, end, (sum + a[pos]) % m, result);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] %= m;
    }

    int mid = n / 2;
    vector<long long> left, right;
    left.reserve(1ULL << mid);
    right.reserve(1ULL << (n - mid));
    dfs(0, mid, 0, left);
    dfs(mid, n, 0, right);
    sort(right.begin(), right.end());

    long long ans = 0;
    for (long long u : left) {
        // 查找严格小于 m-u 的最大余数，确保相加后不回绕。
        auto it = lower_bound(right.begin(), right.end(), m - u);
        // 空集保证 right 含 0，而 m-u >= 1，所以前驱一定存在。
        --it;
        ans = max(ans, u + *it);
    }

    cout << ans << '\n';
    return 0;
}

代码中二分所得位置一定有前驱：$B$ 含空集对应的 $0$，且 $m-u\ge1$。当 $m=1$ 或左半没有元素时，这个性质仍然成立。

设 $L=2^{\lfloor n/2\rfloor}$、$R=2^{\lceil n/2\rceil}$，则生成状态需 $O(L+R)$，排序需 $O(R\log R)$，查询需 $O(L\log R)$。总时间为：

空间为 $O(L+R)$。常见的简写是时间 $O(n2^{n/2})$、空间 $O(2^{n/2})$。估算运行量时，别漏掉排序，也别把所有基本操作当成相同耗时。

五、 经典应用范式：合并时究竟查询什么？

下面几种是常见入口。它们的区别主要在查询目标，同一道题也可能同时使用排序、二分和状态压缩，不必把工具理解成彼此排斥的分类。

5.1 范式一：精确补数——判定与计数

若要找 $u+v=T$，固定 $u$ 后，只需查询 $v=T-u$。

• 只问是否存在：右半使用哈希集合，或排序后二分判定。
• 统计方案数：右半保存每个和出现的次数，查询 count[T-u]；也可排序后用 equal_range 得到出现区间。
• 若两个数组都压成“值、次数”，某对补数的贡献是左右次数之积。

例如左半有两个不同子集的和都是 $3$，右半有三个不同子集的和都是 $7$，目标为 $10$，它们贡献的是 $2\times3=6$ 个方案。

这一范式也适用于异或：若 $u\mathbin{\oplus}v=k$，需要的搭档就是 $k\mathbin{\oplus}u$。变化的是运算关系，固定一半查补数的动作没有变。

5.2 范式二：有界最值——排序与二分

若目标是 $u+v\le T$ 且尽量大，固定 $u$ 后找：

实现时用 upper_bound(B.begin(), B.end(), T-u) 的前驱；若没有前驱，则当前 $u$ 没有合法搭档。

CF 888E 化简后的条件是严格小于 $m-u$，所以使用 lower_bound 的前驱。二分函数应由不等号推出来，不能只记一个函数名。

如果改成“总和最接近 $T$”，则检查 $T-u$ 附近的前驱和后继，因为最佳搭档可能在阈值的任意一侧。

5.3 范式三：单调边界——双指针扫描

仍考虑 $u+v\le T$，但这次要求方案数。将两边都升序排序，从小到大枚举 $A$ 中的 $u$，维护右半最后一个合法下标 $j$：

1
2
3
4
5
6
7
8

int j = static_cast<int>(B.size()) - 1;
long long ans = 0;
for (long long u : A) {
    while (j >= 0 && u + B[j] > T) {
        --j;
    }
    ans += j + 1;
}

对当前 $u$，$B[0\ldots j]$ 全部合法，贡献 $j+1$。随着 $u$ 增大，阈值 $T-u$ 只会减小，因此 $j$ 只会向左移动。排序之后，合并只需 $O(L+R)$。

这里的 $A,B$ 保留每个子集对应的记录，包括重复和；答案及加法都要使用能够容纳题目范围的整数类型。

双指针不是多属性问题的专属工具。只要查询边界具有这种单调变化，就可以考虑把多次二分换成一次扫描。

5.4 范式四：多属性最优——重量排序与前缀最大值

一般的 0-1 背包中，每个物品有重量和价值。若物品数只有三十左右、重量和价值范围都很大，可以枚举每半边所有的 $(w,v)$。

固定左半状态 $(w_L,v_L)$ 后，右半应回答：

右半按重量排序以后，不能简单取“重量最大但仍合法”的那个状态，因为它的价值未必最大。需要再预处理前缀最大价值，二分找到合法前缀末尾，然后取该前缀的最大价值。

例如右半按重量排序为：

剩余容量为 $3$ 时，答案应是价值 $5$，而不是重量 $3$ 的状态所对应的价值 $4$。

还可以删除被支配的状态：若某状态重量更大或相等、价值却更小或相等，那么任何能容纳它的搭档，也能容纳更轻且价值不低的替代状态。这种删除对“只限制重量、只最大化价值”的模型是安全的；添加选取个数等条件后，需要重新判断，必要时按个数分组处理。

六、 不只是切数组：把搜索过程从中间接起来

有时切开的对象是决策过程。以只许向右或向下的网格路径为例，从起点到终点的总步数固定为 $n+m-2$，可以按走过的步数选一条中间反对角线。

从起点走到这条线，枚举前半条路径；从终点反向走到这条线，枚举后半条路径。合并时必须在同一个格子相遇，所以状态里要保存位置，不能把所有半路径的值混在一起配对。

若两半的异或值 $x,y$ 都包含相遇格子的值 $a_{i,j}$，完整路径的异或值就是：

原因是相遇格子在两半中各计了一次，直接异或会抵消，需要再补一次。要达到目标 $k$，固定前半条路径以后，需要在同一相遇格子的后半状态里查找：

这又回到了“精确补数”的查询。切分对象变了，核心动作相同。

路径正向约束必须能反向枚举，并且中间状态要足以判断兼容性。一般图上的两段路径若还要求顶点互不重复，只存终点和路径长度就不够；它们可能在其他位置重叠。

折半搜索与双向 BFS 都会让人想到“从两边在中间相遇”。双向 BFS 通常按层寻找最短路；这里的折半枚举是在整理半边选择，再匹配、计数或优化，未必是在求最短路，也未必真的从两个端点出发。

七、 什么时候有效，什么时候还不够？

1. 尽量平衡的是状态量

每个元素都是二选一时，左右元素个数接近，生成的状态数也最接近。所以常取 $\lfloor n/2\rfloor$ 和 $\lceil n/2\rceil$。

若各变量的选择数不同，则应该尽量平衡两边选择数的乘积，而不只是元素个数。某一半还要排序或保存大状态时，也可以根据时间、空间限制适当调整切分。

2. 空间是需要付出的代价

当 $n=40$ 时，两半共有约 $2\times 2^{20}$ 个状态。若每个状态只是一个 8 字节整数，仅状态数据约占 $16$ MiB；若还存重量、价值、掩码，或使用哈希表，空间会增加。

可以只保存一边，另一边 DFS 到叶子时立即查询，降低存储量。这是实现上的取舍，通常不会改变最坏时间复杂度的数量级。

3. 全局条件不一定阻止折半

“恰好选 $k$ 个”可以记录半边的选取个数 $c_L,c_R$，只匹配 $c_L+c_R=k$ 的组。跨越两半的条件，只要能用足够小的状态表达，仍然可以处理。

真正困难的是：为了判断两半是否兼容，必须保存庞大的细节，或者每次仍要逐个检查另一半。此时“切成两半”本身还不足以给出高效算法。

4. 为什么不继续切成四份？

只看枚举量，四份各自确实更小。但最终需要合并四份。若先把两两组合显式生成，每个组合数组又可能有 $2^{n/2}$ 个状态，未必比两半更省。

两半的便利在于：固定一边以后，另一边经常恰好是一个成熟的查询问题。继续切分是否有收益，需要新的合并方法和复杂度分析。

八、 推荐题目：每道题练一个不同的合并动作

建议先做“只有一个属性”的题，再进入多属性或路径状态。下面按学习目标安排；“送礼物”虽然模型直接，但完整数据规模比前两道更大，不必把它当成最轻松的实现练习。

每道题开始前，先用一句话回答“固定左半后，我要向右半查什么”，再动手写 DFS。

8.1 从 888E 到计数：世界冰球锦标赛

该题有至多 $40$ 场比赛，预算可达 $10^{18}$，统计总票价不超过预算的选择方案数。固定左半花费 $u$，右半应提供所有不超过 $M-u$ 的状态数量，可以用 upper_bound，也可以使用前面的双指针。P4799 题面

做完后应能解释：为什么两个票价相同的比赛仍然可能对应不同方案，为什么不能把右半子集和直接去重。

8.2 从二选一到多选项：方程的解数

该题要求统计 $\sum k_ix_i^{p_i}=0$ 的整数解，$n\le6$，每个 $x_i$ 在 $[1,m]$ 内取值，$m\le150$。直接枚举可能达到 $150^6$，分成各三个变量后，每边最多 $150^3=3\,375\,000$ 个状态。P5691 题面

它能纠正一个常见印象：折半搜索不专属于子集，也不一定由 $n\approx40$ 触发。这里应观察的是搜索分支数的乘积。固定一半表达式的值 $u$，查询另一半的值 $-u$ 出现多少次。

8.3 从模型直接到规模估算：送礼物

该题求总重量不超过 $W$ 的最大子集和，$n\le46$。最均衡切分时，每边可能有 $2^{23}$ 个状态；一边仅存 8 字节整数，原始数据就约 $64$ MiB。可以考虑只存一边、另一边边搜边查，并结合正重量带来的安全剪枝。P10484 题面

它适合检验：你是否会在写代码前把枚举、排序、存储的成本分别算清，而不是看到“折半”就默认一定很快。

8.4 从子集和到多属性：ABC032 D

该题保证三类条件至少满足一类：$n\le30$，或者每个物品的重量较小，或者每个物品的价值较小。折半搜索解决的是 $n\le30$ 的分支；完整解法还需要按重量或按价值的 DP，不能对所有输入都直接折半。ABC032 D 题面

它很适合回看开头的“暗号”：物品数小、重量范围小、价值范围小，分别允许你在哪一个维度上付出代价？

8.5 从切数组到切路径：Xor-Paths

该题在至多 $20\times20$ 的网格上，只允许向右或向下移动，统计路径异或值为 $k$ 的方案数。尝试沿中间反对角线相遇，并把状态按相遇格子分别保存。CF 1006F 题面

做到这里，应该能独立写出合并式，并解释为什么两条半路径的异或值不能直接相等或直接异或成 $k$。

九、 动手前的五个检查

1. 完整选择是什么？ 先明确暴力究竟在枚举哪些决策，计算它的规模。
2. 切开会不会丢条件？ 每个完整方案是否唯一对应一对半边方案，兼容条件如何保存？
3. 另一半需要回答什么？ 把条件化成精确补数、阈值查询或带属性的最优查询。
4. 状态能不能压缩？ 最值、计数、恢复方案需要的信息不同；去重和删劣解都要有理由。
5. 总成本有没有算全？ 把生成、排序、查询和内存分别估算，确认合并没有退回两两枚举。

可以先遮住代码，用四个数手算一次两半状态和查询过程。若你能说清某个左半状态向右半“要的是什么”，就已经抓住了折半搜索最值得迁移的部分。

10 相关题解