You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n) in such a way that the value of 
Print the maximum possible value of
The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Print the maximum possible value of
4 4 5 2 4 1
3
3 20 199 41 299
19
In the first example you can choose a sequence b = {1, 2}, so the sum 
In the second example you can choose a sequence b = {3}.
题意:n个数中取若干个数,求sigma%m最大值为多少
思路:折半搜索+二分搜索[套路]
1.折半搜索,这题一共有35个数,很显然暴力不行.
2.先二进制暴力枚举一半,求出所有可能O(1e6),sum.
3.再二进制暴力枚举另一半,求出所有可能 sum1
4. sum1 <m && sum <m 求 max ((sum+sum1)%m)
5.
sum1+sum一共两种情况
一:2*m>=sum1+sum >=m 那么一定有sum越大越好
二:sum1+sum<=m 那么最大值存在于m-sum1-1
#include<bits/stdc++.h>
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int N=1e5+50;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
ll a[50];
vector <ll> vec;
int main(void){
ll n,m;
cin >>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]%=m;
ll nn=n/2;
for(int i=0;i<=(1<<nn)-1;++i){ //二进制枚举状态
ll sum=0;
for(int j=0;j<=20;j++){
int t=1&(i>>j); //位运算判断当前数加或者不加
if(t==1) sum+=a[j+1];
}
sum%=m;
vec.push_back(sum);
}
sort(vec.begin(),vec.end());
ll mx=-1;
for(int i=0;i<=(1<<(n-nn))-1;++i){
ll sum=0;
for(int j=0;j<=20;j++){
int t=1&(i>>j);
if(t==1) sum+=a[j+nn+1];
}
sum%=m;
auto it=prev(lower_bound(vec.begin(),vec.end(),m-sum));//小技巧,寻找<=m-sum-1中最大的,即找到 第一个>=m-sum的数 的前一个数
mx=max(mx,*it+sum);
mx=max(mx,(*vec.rbegin()+sum)%m);
}
cout << mx << endl;
return 0;
}
/**************
10 1000
16140 63909 7177 99953 35627 40994 29288 7324 44476 36738
**************/
京公网安备 11010502036488号