给定⼀个包含 n 个正整数的序列，再给定⼀个正整数 m。
请你求出该序列的⼦序列的各元素之和对 m 取模的最⼤值。
输⼊格式
第⼀⾏包含两个整数 n 和 m。
第⼆⾏包含 n 个正整数。
输出格式
输出⼀个整数表示结果。
数据范围
\(1≤n≤34\)
\(1≤a_i≤10^9\)
\(1≤m≤10^9\)
输⼊样例：
3 5
2 7 8
输出样例
4
解题
直接查找的话，\(2^{34}\)显然超时，但是如果折半搜索，最后尝试将两部分答案合并，\(2^{17}\times 2\)应该是可以的
#include <bits/stdc++.h>
using namespace std;int n,n1,n2,m,a1[50],a2[50],tmp,mx=-1;
set<int> s1,s2;void dfs1(int now,int s){if (now==n1+1){s1.insert(s);return;}else{dfs1(now+1,(s+a1[now])%m);dfs1(now+1,s);}
}
void dfs2(int now,int s){if (now==n2+1){s2.insert(s);return;}else{dfs2(now+1,(s+a2[now])%m);dfs2(now+1,s);}
}int main(){scanf("%d%d",&n,&m);n1=n/2;n2=n-n1;for (int i=1;i<=n1;i++){scanf("%d",&tmp);a1[i]=tmp%m;}for (int i=1;i<=n2;i++){scanf("%d",&tmp);a2[i]=tmp%m;}dfs1(1,0);dfs2(1,0);for (auto i=s1.begin();i!=s1.end();i++){auto it=upper_bound(s2.begin(),s2.end(),m-*i-1);it--;int itn=*it;mx=max(mx,itn+*i);}printf("%d",mx);return 0;
}我们用a1储存前一半序列，a2储存后一半，而集合s1、s2分别储存前后两半序列所有子序列和模m可能的值，使用set的原因一是set可以自动去重，二是set会将insert的数自动排序，省去了一步sort
我们看主函数中调用dfs之后的部分，也就是合并答案的部分。我们先遍历s1中每个数（假设当前数是now，代码中为*i），最好的情况当然是最大值即为m-1，也就是在s2中存在一个m-now-1。当然这个数也可能不存在，这时我们就要找到比它小的最大的数，与now相加后就是一个可能的答案。这里我使用upper_bound-1来查询s2中小于等于m-now-1的最大数，代码中即为itn，itn+*i就是一个可能的答案，将其与当前的最大值mx比较即可