详细题解respect！

#include <bits/stdc++.h>
using namespace std;
/*
长度为 n
选若干个数（每个数只能选 0次、1次）可以一个都不选
组成一个子集
求出子集所有元素的和对x取模得到最大值
方法一、
暴力枚举所有子集：2的n次方个子集

折半搜索：（n在30-40）范围子集的专属最优解法
n先分为先半段、后半段
n = 35
前17个  2的17次方：131072 任意子集和 s
后18个  2的17次方：262144 任意子集和 t
max(s+t) % x

如何让取模的结果尽可能大
【0，x-1】   -> x-1


策略：
1、对于每一个左半和s，优先寻找一个最大的t，满足s+t < x
此时(s+t)%x = s+t ,尽可能大
2、若不满足上诉条件的t，那就去选择右半数组的最大 t
此时(s+t)%x = s+t - x ,尽可能大

算法过程：
1、数组拆分将原数组 a 分割为左半数组、右半数组两部分。

2、暴力枚举子集和
分别枚举左右两部分所有子集的和，全部对 x 取模，存入两个独立数组存储。
3、排序预处理
将右半部分所有子集和数组进行升序排序，用于后续二分查找。

4、二分匹配求最优
遍历左半数组的每一个数值 s：
计算上限值 t = x−1−s
二分查找右半数组中小于等于 t 的最大值
根据匹配结果更新全局答案最大值

*/
typedef long long ll;
const int MAX = 1 << 18;// 2^18 = 262144，足够存储35拆半后所有子集和
ll a[40];
ll l[40], r[40];
ll sum_l[MAX], sum_r[MAX];// 存储左右两半所有子集和

// 函数功能：枚举arr所有子集和，对mod取模，存入res数组，返回子集总个数
// 参数：原数组、数组长度、模数、存储子集和的结果数组
int get_sum(ll arr[], int len, ll mod, ll res[])
{
	int cnt = 0;
	// 位运算枚举所有子集，i从0到2^len-1
	for (int i = 0; i < (1 << len); i++)
	{
		ll sum = 0;
		for (int j = 0; j < len; j++)
		{
			// 当前二进制位为1，代表选取该元素
			if (i & (1 << j))
				sum += arr[j];
		}
		res[cnt++] = sum % mod;
	}
	return cnt;
}

int main() {
	ll n,x;
	cin >> n >> x;
	// 原始数组，n最大35，数组开40足够
	for (int i = 0; i < n; i++)	cin >> a[i];
	// 折半分割
	int mid = n / 2;
	// 拆分左半部分
	for (int i = 0; i < mid; i++) l[i] = a[i];
	// 拆分右半部分
	for (int i = 0; i < n - mid; i++) r[i] = a[mid + i];
	int cnt_l = get_sum(l, mid, x, sum_l);//获得子集和的总个数，并依次存到sum_r和l
	int cnt_r = get_sum(r, n - mid, x, sum_r);
	// 右半数组排序，用于二分查找
	sort(sum_r, sum_r + cnt_r);
	ll ans = 0;
	for(int i=0;i<cnt_l;i++){
		ll s = sum_l[i];
		ll t = x-1-s;
		ll *p = upper_bound(sum_r,sum_r+cnt_r,t);
		ll cur;
		if(p != sum_r){
			p--;//向前移动1为，即 <= t的最大值
			cur = s + *p;
		}else{
			cur = s + sum_r[cnt_r-1]-x;
			// 无满足条件的值，选取右半最大元素
		}
		ans = max(ans,cur%x);
	}
	cout<<ans<<endl;
	return 0;
}//Tian