【CF888E】Maximum Subsequence

题意：给你一个序列{ai}，让你从中选出一个子序列，使得序列和%m最大。

n<=35，m<=10^9

题解：不小心瞟了一眼tag就一下子知道怎么做了，吓得我赶紧把tag屏蔽了。

我们将原序列拆成两半，每一部分都暴力搜索出所有的子序列之和，用set存起来。然后枚举前一半的所有子序列和，设其为x，则使得总和%m最大的右半部分子序列和一定是所有<m-x的数中最大的那个，在set里找一下前驱就行了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n,k,m,cnt,ans;int v[40],p[(1<<18)+4];set
         
           s;set
          
           ::iterator it;void dfs(int x,int sum){ if(x>k) { p[++cnt]=sum,ans=max(ans,sum); return ; } dfs(x+1,sum),dfs(x+1,(sum+v[x])%m);}int main(){ scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++) scanf("%d",&v[i]),v[i]%=m; k=n/2,dfs(1,0); for(i=1;i<=cnt;i++) s.insert(p[i]); cnt=0,k=n,dfs(n/2+1,0); for(i=1;i<=cnt;i++) { it=s.lower_bound(m-p[i]); if(it==s.begin()) it=s.end(); it--; ans=max(ans,(p[i]+(*it))%m); } printf("%d",ans); return 0;}