Module: 在中间相遇


Problem

1 /5


模最大子序列

Theory Click to read/hide

中间相遇
Meet-in-the-middle - 一种优化方式解决方案,包括将原始问题分成两半,分别独立解决,然后通过合并两半的解决方案来获得原始问题的解决方案。

因此,如果满足两个条件,则使用meet-in-the-middle 是有意义的。
1) 解决一半问题所需的时间渐近小于解决整个问题的时间。
2) 通过解决半个问题,可以得到原整个问题的解,同时比只解决整个问题渐进地更快。
 
例子
假设有四个整数数组 ABCD。有必要从每个数组中恰好选择一个数字,使这些数字的总和等于零。您可以使用一种简单的解决方案,即简单地枚举所有可能的选项。这适用于 O(n4)

然而,我们可以使用meet-in-the-middle
请注意,a + b + c + d = 0 等同于 (a + b) = -(c + d)
让我们把任务分成两半,即前半部分我们将只使用数组AB,后半部分只使用CD
让我们在前半部分遍历所有可能的(a + b)选项,并将所有值存储在哈希表中(unordered_mapHashMap 之类的。)。这在 O(n2) 中有效。
现在我们将在下半部分迭代所有可能的选项 (c + d)。在考虑某个选项时,我们会检查哈希表中是否有与当前符号相反的和相关联的值(然后我们找到两个倒数加起来为零)。这部分也适用于 O(n2)
我们这里没有单独的“answer merge”阶段;一方面,我们在解决每一半的过程中这样做了。大多数任务都会有类似的情况。
我们最终在 O(n2) 中使用 meet-in-the-middle 解决了这个问题。

值得注意的是,meet-in-the-middle 在优化指数解时最常使用,这会显着影响运行时间。

Problem

给定一个数组 A,它由 n 个正整数和一个数字 m 组成。 选择位置序列 B 1B2,...,Bk (1 <= B1 < B2 < ... < Bk <= n) 这样   ; \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) 是最大值(即,使得 子序列的元素之和除以数m的余数是最大可能的)。 选择的序列可以为空。
计算\((\sum_{i=1}^{k} A_{B_i}) mod \; m\)的最大可能值。

输入
第一行包含两个整数 nm (1 <= n <= 35, 1 <= m <= 109). 第二行包含n个整数A1,A2, ..., An (1 <= Ai <= 109 )< br />
印记
输出一个数-最大值 \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 
例子
<头> <正文>  
说明
在第一个示例中,您可以选择 B = {1, 2}(A1 + A2) mod m = (5 + 2) % 4 = 3.
在第二个示例中,您可以选择 B = {3}
# 输入 输出
1 4 4
5 2 4 1
3
2 3 20
199 41 299
19