一个优化暴力的知名小 trick，早就知道，记一下。
没啥好的题，手搓一道吧：
给定一个 \(n\times n\) 矩阵，第 \(i\) 行第 \(j\) 列元素为 \(a_{i,j}\)，求是否存在一条左上到右下的路径（只能向右走或向下走），使得元素和是 \(p\) 的倍数？
\(n\le 18\)，\(p\le 10^9\)。
总共需要走 \(34\) 步，路径总数不超过 \(2^{34}=17179869184\)。或者更确切地，为 \(\binom{34}{17}=2333606220\)，我们无法枚举（因为复杂度还会乘 \(\mathcal O(n)\)）。
我们想到，如果能只走 \(17\) 步的话就好了。
于是我们发现确实可以做到。副对角线是矩阵的一个天然分界线，从左上角走到副对角线的路径总数为 \(2^{17}=131072\) 种，从右下角也一样。我们处理出左上路径 \(131072\) 种可能的元素和并插到 set 中，然后枚举右下路径的可能情况，找找 set 中是否存在 \(p-x\) 即可。
于是时间复杂度被我们从 \(\mathcal O(2^{2n}n)\) 优化到了 \(\mathcal O(2^nn)\)。
这就是 meet-in-the-middle 的 trick，这类题目的显著特征是数据范围在 \(30\sim 40\) 之间（例如本题中的数据范围实际是 \(2n=36\)），此时 \(\mathcal O(2^{n+o(1)})\) 的暴力无法通过，希望将复杂度开平方。此时我们将问题分为两个规模为 \(\frac{n}{2}\) 的小问题，并且试图在能接受的复杂度内合并两个小问题的答案。
双向 bfs 其实也是利用了这个 trick。
标签：17,复杂度,路径,34,trick,middle,mathcal,meet From： https://www.cnblogs.com/ruierqwq/p/meet-in-the-middle.html