-
分析
看到 \(n \leq 35\) 的数据范围就想到了 meet-in-middle。
先爆搜出对于 \(1 \sim \frac{n}{2}\) 和 \(\frac{n}{2} \sim n\) 两个下标范围内在模意义下所有的和。
然后用一个常见 trick，就是枚举第二个部分的和，然后匹配第一个部分的和的最优解。显然匹配有两种情况，一种是小于模数，一种是比模数大。
比模数大的情况还要取模，但是我们发现对于 \(\forall a,b < m, a + b >= m\)，有 \(a + b < 2m\)，所以最多只需要减一个模数，那么模后的式子变成了 \(a + b - m\)，但是因为 \(b < m\)，所以 \(a + b - m < a\)，然后我们发现这种情况还没有第一个部分什么都不取，只取第二个部分优，所以排除掉这个情况。那么只剩下和小于模数的情况，即 \(a + b < m\) 的情况。\(b\) 一定，\(a\) 越大，和越大，所以要找到使得 \(a + b < m\)，即满足 \(a < m - b\) 的最大 \(a\)。
小于 \(m - b\) 的最大值，想到二分，但是二分需要单调性，于是先将 \(a\) 数组排序后再二分，这样问题就就解决了。
总时间复杂度 \(\mathcal{O(2^{\frac{n}{2}} \log 2^{\frac{n}{2}})}\)，可以通过本题。 -
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
constexpr int MAXN(1000007);
int fr[MAXN], a[MAXN];
int n, mod, cnt, ans;
inline void read(int &temp) { cin >> temp; }
void dfs1(int x, int sum) {
if (x == n / 2 + 1) return fr[++cnt] = sum, void();
dfs1(x + 1, sum);
dfs1(x + 1, (sum + a[x]) % mod);
}
void dfs2(int x, int sum) {
if (x == n + 1) return ans = max(ans, fr[lower_bound(fr + 1, fr + cnt + 1, mod - sum) - fr - 1] + sum), void();
dfs2(x + 1, sum);
dfs2(x + 1, (sum + a[x]) % mod);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n), read(mod);
for (int i(1); i <= n; ++i) read(a[i]);
dfs1(1, 0);
sort(fr + 1, fr + cnt + 1);
dfs2(n / 2 + 1, 0);
cout << ans << endl;
return 0;
}