题解 | 模意义下最大子序列和（Easy Version）

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int n, m;
ll maxVal = 0;
int vis[16], a[16];

//这题和之前的全排列有相似之处，这个是顺序遍历每个数字，每个数字选和不选，当遍历完就结算
//全排列是顺序遍历每个位置，每个位置不能选重复，遍历完结算
//对于排列的组合数是可以用快速幂的技巧求C(m, n)或A(m, n),但是要知道每种组合具体是什么需要搜索，复杂度o(2 ^ n)
void dfs(int deep, int *vis) {
	if (n + 1 == deep) {
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += vis[i] ? a[i] : 0;
		}
//		cout << ans % m << " ";
		maxVal = max(ans % m, maxVal);
		return;
	}
	vis[deep] = 1;
	dfs(deep + 1, vis);
	vis[deep] = 0;
	dfs(deep + 1, vis);
	//回溯的部分 
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
	}
//	cout << "Origin:" << maxVal;
    dfs(1, vis);
    cout << maxVal << endl;
//    cout << "maxVal:" << maxVal << endl; 
}
// 64 位输出请用 printf("%lld")