超时程序

$$ N 为 34, 我首先想到一个O(2^N × log(2^N)) 的算法 2^{34} = 17179869184严重超时 $$

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    set<int> st;
    st.insert(0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        vector<int> v;
        int x;
        scanf("%d", &x);
        for (auto y : st) {
            v.push_back((x + y) % m);
        }
        for (auto y : v) {
            ans = max(ans, y);
            st.insert(y);
        }
    }
    printf("%d", ans);
    return 0;
}

优化一下 AC

$$ 如果把这N个数平均分成两份，N1，N2\\\\ 分别求所有可行方案,复杂度为O(2^{(N/2)} * log(2^{(N/2)}))\\\\ 得到两个集合S1, S2.\\\\ 对于每个a属于S1，可以在S2中二分得一个最优解\\\\ 总复杂度还是O(2^{(N/2)} * log(2^{(N/2)}))\\\\ $$

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50;
int a[MAXN];
int n, m;

vector<int> work(int l, int r) {
    vector<int> res;
    set<int> st;
    st.insert(0);
    for (int i = l; i <= r; i++) {
        vector<int> v;
        int x = a[i];
        for (auto y : st) {
            v.push_back((x + y) % m);
        }
        for (auto y : v) {
            st.insert(y);
        }
    }
    for (auto y : st) {
        res.push_back(y);
    }
    return res;
}

int check(int x, vector<int> &v) {
    int l = 0, r = (int)v.size() - 1;
    int res = (x + v[r]) % m;
    int w = m - 1 - x;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int k = v[mid];
        if (k > w) {
            r = mid - 1;
        } else {
            res = max(res, (x + k) % m);
            l = mid + 1;
        }
    }
    return res;
}

int main() {

    scanf("%d%d", &n, &m);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);// don't forget &
    }
    if (n == 1) {
        printf("%d", a[1] % m);
        return 0;
    }

    int k = n / 2;

    vector<int> b = work(1, k);
    vector<int> c = work(k + 1, n);
    int ans = 0;
    for (auto x : b) {
        ans = max(ans, check(x, c));
    }
    printf("%d", ans);
    return 0;
}

不知到有没有更好的做法