CF888E题解

• 分析

  看到 \(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;
}