結果
| 問題 | No.1645 AB's abs |
| ユーザー |
 wait_sushi
|
| 提出日時 | 2021-08-13 22:15:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 28 ms / 2,000 ms |
| コード長 | 5,914 bytes |
| コンパイル時間 | 2,359 ms |
| コンパイル使用メモリ | 211,332 KB |
| 最終ジャッジ日時 | 2025-01-23 19:43:53 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#define endl "\n"using namespace std;typedef long long ll;typedef vector<ll> vl;typedef pair<ll, ll> PP;#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#pragma GCC target("avx")#define overload4(_1, _2, _3, _4, name, ...) name#define overload3(_1, _2, _3, name, ...) name#define rep1(n) for (ll i = 0; i < n; ++i)#define rep2(i, n) for (ll i = 0; i < n; ++i)#define rep3(i, a, b) for (ll i = a; i < b; ++i)#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define rrep1(n) for (ll i = n; i--;)#define rrep2(i, n) for (ll i = n; i--;)#define rrep3(i, a, b) for (ll i = b; i-- > (a);)#define rrep4(i, a, b, c) \for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)#define rrep(...) \overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)#define elif else ifll beki(ll i) { return 1ll << i; }#define skip(M) \if (M) \continue#define all(v) v.begin(), v.end()#define allm(x, y, M) for (auto [(x), (y)] : (M))#define alls(i, S) for (auto(&i) : (S))#define pb push_back#define fi first#define se second#define outno \print("NO"); \returnconst ll INF = (1LL << 61) - 1;const ll MOD = 1000000007;const ll MOD2 = 998244353;const ll MAX_N1 = 200010;const ll MAX_N2 = 500010;template <class X> void print(X x) { cout << x << endl; }void print(vl x) {for (ll i : x) {cout << i << " ";}cout << endl;}void print(vector<PP> x) {for (PP i : x) {cout << i.first << " " << i.second << endl;}cout << endl;}template <class X> int lbound(vector<X> &Y, X a) {return lower_bound(all(Y), a) - Y.begin();}template <class X> int ubound(vector<X> &Y, X a) {return upper_bound(all(Y), a) - Y.begin();}template <class X> X lbound2(vector<X> &Y, X a, int mode = 0) {int x = lbound(Y, a) - mode;if (x < 0 || x >= Y.size())return INF;return Y[x];}template <class X> X ubound2(vector<X> &Y, X a, int mode = 0) {int x = ubound(Y, a) - mode;if (x < 0 || x >= Y.size())return INF;return Y[x];}template <class... T> void cl(T &... t) { (..., (t.clear())); }template <class... T> void in(T &... t) { (..., (cin >> t)); }template <class... T> void put(vl &V, int n, int mode = 0) {ll k;if (mode == 0)cl(V);rep(i, n) {cin >> k;V.pb(k);}}int max_index(vl &V) { return max_element(all(V)) - V.begin(); }int min_index(vl &V) { return min_element(all(V)) - V.begin(); }ll sum(vl &V) { return accumulate(all(V), 0ll); }template <typename T> void UNIQUE(vector<T> &v) {sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}template <typename T> T ADD(T a, T b) {T res;return __builtin_add_overflow(a, b, &res) ? numeric_limits<T>::max() : res;}template <typename T> T MUL(T a, T b) {T res;return __builtin_mul_overflow(a, b, &res) ? numeric_limits<T>::max() : res;};template <typename T> T POW(T a, int n) {T res = 1;for (; n > 0; n >>= 1, a *= a)if (n & 1)res *= a;return res;}template <class X> bool ma(X &a, X b) {if (a < b) {a = b;return true;}return false;}template <class X> bool mi(X &a, X b) {if (a > b) {a = b;return true;}return false;}void vset(vl &A, ll n, ll k) { A = vl(n, k); }void so(vl &A) { sort(all(A)); }ll age(ll x, ll y) { return (x + y - 1) / y; }ll a, b, c, d, aa, bb, cc, dd, h, x, y, z, p, q, n, t, r, k, w, l, ans, m, u, v;ll codeforces = 1;string S, T, U;vl A, B, C, D;vector<vl> g[MAX_N2];vector<PP> VP, VP2;set<ll> s1, s2;#include <cstdint>template <std::uint_fast64_t Modulus> class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};using mint = modint<MOD2>;const int kk = 10010;mint X[101][kk * 2 + 1];void solve() {in(n);put(A, n);X[0][kk] = 1;rep(i, n) {rep(j, kk * 2 + 1) {if (j + A[i] < kk * 2 + 1)X[i + 1][j + A[i]] += X[i][j];if (j - A[i] > -1)X[i + 1][j - A[i]] += X[i][j];}}mint ans = 0;rep(i, kk * 2 + 1) {t = i - kk;ans += X[n][i] * abs(t);}print(ans.a);}int main() {cout << fixed << setprecision(15);cin.tie(0);ios::sync_with_stdio(false);// cin >> codeforces;while (codeforces--) {ans = 0;solve();}}