给一个数列和m，在数列任选若干个数，使得他们的和对m取模后最大（ \(1<=n<=35\) , \(1<=m<=10^{9}\)）

考虑把数列分成两份，两边分别暴力求出所有的可能，那么对于一个数列中每一个数字\(x\)，另一个数列加上它之后小于\(m\)的那个数是最优的，用双指针可以做到\(O(2^{n/2})\)

如果最终的答案是两个数列中的数加起来且大于\(m\)的，因为所有可能都是在模意义下，所以肯定是两个数列中最大的数加起来最优，判断一下就好了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=(1<<18)+5;int n,P,lim,f[N],g[N],a[55],tf,tg,ans;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}void dfs1(int pos,int lim,int res){    if(pos==lim)return (void)(f[++tf]=res,f[++tf]=add(res,a[pos]));    dfs1(pos+1,lim,res),dfs1(pos+1,lim,add(res,a[pos]));}void dfs2(int pos,int lim,int res){    if(pos==lim)return (void)(g[++tg]=res,g[++tg]=add(res,a[pos]));    dfs2(pos+1,lim,res),dfs2(pos+1,lim,add(res,a[pos]));}int main(){//  freopen("testdata.in","r",stdin);    n=read(),P=read(),lim=n>>1;    fp(i,1,n)a[i]=read()%P;    if(n==1)return printf("%d\n",a[1]),0;    dfs1(1,lim,0),dfs2(lim+1,n,0);    sort(f+1,f+1+tf),sort(g+1,g+1+tg);    for(R int i=1,j=tg;i<=tf;++i){        while(f[i]+g[j]>=P)--j;        cmax(ans,f[i]+g[j]);    }cmax(ans,f[tf]+g[tg]-P);     printf("%d\n",ans);return 0;}