[Educational Codeforces Round 32][Codeforces 888E]Maximum Subsequence

    题意：给出\(a[1]\cdot a[n]\)，求一个子序列\({b_n}\)，最大化 \(sum=\sum_{}^{}b_n\ mod\ m\)。\(1<=n<=35,1<=m<=10^9\)

    题解：将序列分成左右两半，分别求出所有可能的和，然后对其中一个求出的和序列的所有元素，在另一个和序列二分查找出与其相加结果最大的值。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1<<18;

int a[maxn],b[maxn],an,bn;
int arr[maxn];
int n,m,ans;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&arr[i]);
	an=bn=1;
	for (int i=1;i<=n/2;i++)
	{
		for (int j=0;j<an;j++) a[j+an]=(a[j]+arr[i])%m;
		sort(a,a+an*2);
		an=unique(a,a+an*2)-a;
	}
	for (int i=n/2+1;i<=n;i++)
	{
		for (int j=0;j<bn;j++) b[j+bn]=(b[j]+arr[i])%m;
		sort(b,b+bn*2);
		bn=unique(b,b+bn*2)-b;
	}
	for (int i=0;i<an;i++)
	{
		int x=lower_bound(b,b+bn,m-a[i]-1)-b;
		if (b[x]!=m-a[i]-1) x--;
		ans=max(ans,a[i]+b[x]);
	}
	printf("%d\n",ans);
	return 0;
}