题意：给一个数列和m，在数列任选若干个数，使得他们的和对m取模后最大。

注意到n<=35，直接枚举状态不行，考虑meeting in the middle。

那么的话我们直接暴力枚举两边的状态就好了，不过我们记录的是取模后的sum。。

现在主要解决合并答案的问题。都是套路是吧。。。

我们容易发现，如果我们枚举一边的答案，

另外一边有用的答案（有可能和当前枚举的构成最后答案的）仅有两种可能，

一种是和当前答案加起来＜模数的，那么显然最大的那个最优，

另一种是＞模数的，由于之前取了模，和不会超过二倍模数，那么显然也是最大的最优。

那么可以直接排序后一遍扫。我比较傻，直接二分查找的，多带了个ｌｏｇ也过了。

 

1 #include 
      
        2 using namespace std; 3 inline int gi() { 4     int w=0,x=0; char ch=0; 5     while (!(ch>='0'&&ch<='9') ) { 6         if (ch=='-') w=1; 7         ch=getchar ();         8     } 9     while (ch>='0'&&ch<='9') {10         x=(x<<3)+(x<<1)+(ch^48);11         ch=getchar ();12     }13     return w?-x:x;14 }15 16 const int MAXN=262144;17 int n,l,r,Mid,Ans,Mod,cntL,cntR,a[40],LefANS[MAXN],RigANS[MAXN];18 19 void _DFS (int x,int sum) {20     if (x==(n>>1)+1) {21         LefANS[++cntL]=sum;22         return;23     }24     _DFS (x+1,sum);25     _DFS (x+1,(sum+a[x]%Mod)%Mod);26 }27 28 void _dfs (int x,int sum) {29     if (x==n+1) {30         RigANS[++cntR]=sum;31         return;32     }33     _dfs (x+1,sum);34     _dfs (x+1,(sum+a[x]%Mod)%Mod);35 }36 37 int search (int id) {38     l=1,r=cntR;39     while (l
       
        >1;41         if (LefANS[id]+RigANS[Mid]>=Mod) r=Mid;42         else l=Mid+1;43     }44     return r-1;45 }46 47 int main ()48 {49     // BY BHLLX50     n=gi (), Mod=gi ();51     for (int i=1;i<=n;++i) a[i]=gi ();52     _DFS (1,0),_dfs ((n>>1)+1,0);53     sort (LefANS+1,LefANS+cntL+1);54     sort (RigANS+1,RigANS+cntR+1);55     for (int i=1;i<=cntL;++i) 56         Ans=max (Ans,max (LefANS[i]+RigANS[search (i)],(LefANS[i]+RigANS[cntR])%Mod));57     printf ("%d\n", Ans);58     return 0;59 }