题解

折半搜索板子题。

发现应当使用搜索，但是爆搜会T，而且刚好可以通过 $O(2^{n/2})$ 的数据，容易联想到折半搜索。

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
ll n,m,s,cnta,cntb,sum,ans;
ll a[35],b[35];
vector<ll> va,vb;
int main(){
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>s;
        if(i<n>>1) a[cnta++]=s;
        else b[cntb++]=s;
    }
    for(ll i=0;i<1<<cnta;i++){
        sum=0;
        for(ll j=0;j<cnta;j++){
            if(i>>j&1){
                sum+=a[j];
                sum%=m;
            }
        }
        va.eb(sum);
    }
    for(ll i=0;i<1<<cntb;i++){
        sum=0;
        for(ll j=0;j<cntb;j++){
            if(i>>j&1){
                sum+=b[j];
                sum%=m;
            }
        }
        vb.eb(sum);
    }
    sort(vb.begin(),vb.end());
    for(auto &i:va){
        auto j=lower_bound(vb.begin(),vb.end(),m-i);
        if(j!=vb.begin()){
            j--;
            ans=max((i+*j)%m,ans);
        }
        ans=max((i+vb.back())%m,ans);
    }
    cout<<ans;
    return 0;
}