E. Maximum Subsequence 二进制折半枚举 二分

传送门

看到每一个元素只存在选与不选两种情况，就想到二进制枚举
但是235会爆，所以折半枚举，另一半用二分找到最佳答案
具体怎么二分呢？
我们注意到 假设m=7 , 左边任意取一个<7的数a，加上右边的任意一个>=m-a的数b,结果mod m 一定是小于等于a的，比如 左边取3，右边最大只能取6 ，(3+6) mod 7 ==3 , 所以 我们二分出来第一个大于等于 m-a 的数（后面的数都不能取，因为取了也绝对不会更大），然后取它之前的数

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 263000;
#define ll long long
#define endl "\n"
#define r0 return 0
map<int, int>mp;

set<int>st;
int a[N], b[N];
int d[40];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        d[i] = temp % m;
    }
    int l = n / 2;
    int top1 = 0, top2 = 0;
    int sum = 0 ;
    for (int i = 0; i < 1 << l; i++)
    {
        sum = 0;
        for (int j = 0; j < l; j++)
        {
            if ((i >> j & 1) == 1) sum = (sum + d[l-1-j]) % m;
        }
        a[++top1] = sum;
    }
    l= n - l;
    sum = 0;
    for (int i = 0; i < 1 << l; i++)
    {
        sum = 0;
        for (int j = 0; j < l; j++)
        {
            if ((i >> j & 1) == 1) sum = (sum + d[n-j -1]) % m;
        }
        b[++top2] = sum;
    }
    sort(b+1, b + 1+top2);
//    sort(a + 1, a + 1 + top1);
    int ans = 0;
    for (int i = 1; i <= top1; i++)
    {
        int tt = m - a[i] ;
        int ff = lower_bound(b + 1, b + 1 + top2, tt) - b;
        ff--;
        ans = max(ans, a[i] + b[ff]);
    }
    cout << ans << endl;
    r0;
}