题目链接
题意:给你两个数n,m,和一个大小为n的数组。
让你在数组找一些数使得这些数的和模m最大。
解法:考虑 dfs但是,数据范围不允许纯暴力,那考虑一下折半搜索,一个从头开始往中间搜,一个从后往中间搜。在中间相遇的时间二分更新最大值即可。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
int n,m,cnt;
int a[37],b[37];
int ans;
int sum1[(1<<20)];
vector<int>v;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i],a[i]%=m,ans=max(ans,a[i]);
for(int i=0;i<(1<<(n/2));i++){
for(int j=0;j<n/2;j++)if(i&(1<<j))sum1[i]=(0ll+sum1[i]+a[j])%m;
ans=max(ans,sum1[i]);
v.pb(sum1[i]);
}
sort(v.begin(),v.end());
for(int i=n/2;i<n;i++)b[cnt++]=a[i];
for(int i=0;i<(1<<cnt);i++){
int A=0;
for(int j=0;j<cnt;j++)if((1<<j)&i)A=(0ll+A+b[j])%m;
ans=max(ans,A);
auto pos=upper_bound(v.begin(), v.end(),m-A-1);
pos--;
ans=max(1ll*ans,(0ll+A+(*pos))%m);
}
cout<<ans%m;
return 0;
}