Submission #5069151

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() = default;
    mint(int32_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator - (mint<MOD> other) const { int32_t c = this->value - other.value; return mint<MOD>(c <    0 ? c + MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    mint<MOD> pow(uint64_t k) const {
        mint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
};


constexpr int MOD = 998244353;
mint<MOD> solve(int n, vector<int> const & a) {
    int sum_a = accumulate(ALL(a), 0);

    vector<mint<MOD> > dp(sum_a + 1);
    dp[0] += 1;
    REP (i, n) {
        REP_R (j, sum_a + 1) if (dp[j].value) {
            dp[j + a[i]] += dp[j];  // c
            dp[j] += dp[j];  // a, b
        }
    }

    vector<mint<MOD> > dp1(sum_a + 1);
    dp1[0] += 1;
    REP (i, n) {
        REP_R (j, sum_a + 1 - a[i]) {
            dp1[j + a[i]] += dp1[j];
        }
    }

    if (sum_a % 2 == 0) {
        return mint<MOD>(3).pow(n) - accumulate(dp.begin() + (sum_a / 2), dp.end(), mint<MOD>()) * 3 + dp1[sum_a / 2] * 3;
    } else {
        return mint<MOD>(3).pow(n) - accumulate(dp.begin() + (sum_a / 2 + 1), dp.end(), mint<MOD>()) * 3;
    }
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    cout << solve(n, a).value << endl;
    return 0;
}

Submission Info

Judge Result