Meet in the middle


例题 - Maximum Subsequence CF - 普及+/提高
例题 - 请努力完成本题，再阅读以下内容。	解答

对于规模较小，但暴力又差一点的问题（一个特征是某些测试点刚好N为最大可解规模的两倍），有时可以用这个优化办法。主要思想是将整个搜索过程分成两半，分别搜索，往往使用vector存储所有生成的搜索结果。最后分别将两半结果排序之后，用二分查找的方式合并结果。总体的效果，就是将复杂度从 $\mathcal{O}(2^n)$ 降低到 $\mathcal{O}(2^\frac{n}{2})$ 。

题解 - Maximum Subsequence

根据meet in the middle的思想，此题解法就是将所有数分成左、右两组，然后分别生成所有子集（最多 $2^{18}$ 个），并求和的模，加入到vector中。然后因为求和取模的运算具有结合率，所以我们对于左侧的任一结果 $x$ ，都取右侧结果中最大的 $y$ ，使得 $x+y \leq m-1$ 。最后在所有 $x+y$ 中取最大值，并与左右侧分别的最大值相比较取更大，就是结果。

注意， $x+y >= m$ 的情况不会对结果有贡献，因为我们有 $(x+y) \mod m < x$ ，所以这种情况 $x+y$ 一定不如单选 $x$ (或 $y$ )更好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;   // n <= 35
int a[40];  
vector<int> ml, mr;
int ans;
 
void generate(int l, int r, vector<int> &res) {
    for (int bm = 0; bm < (1 << (r-l+1)); bm++) {
        int sum = 0;
        for (int i = 0; i < r-l+1; i++) {
            if (bm & (1 << i)) 
                sum = (sum + a[l+i]) % m;
        }
        res.push_back(sum);
    }
    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end()) - res.begin());
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    generate(0, n/2, ml);
    generate(n/2+1, n-1, mr);
    ans = max(ml.back(), mr.back());
    for (int x: ml) {       // merge results with binary search
        auto it = lower_bound(mr.begin(), mr.end(), m-1-x);
        if (it != mr.end() && *it == m-1-x) {
            printf("%d", m-1); return 0;
        }
        if (it == mr.end() || *it > m-1-x && it != mr.begin()) {
            it--;
            ans = max(ans, x + *it);
        }
    }
    printf("%d\n", ans);
    return 0;
}

习题
	CSES	Meet in the Middle		普及+/提高	解答
P8187	USACO Silver	Robot Instructions	2022	提高+/省选-	解答
CF498F	CF	XOR Paths		提高+/省选-	解答
P2962	USACO Gold	Lights	2009	提高+/省选-
	PrepBytes	Proportional Cake		提高+/省选-	解答
	YS	Max Independent Set		提高+/省选-	解答