#1143352 (C++23) No.137 貯金箱の焦り

• 問題: No.137 貯金箱の焦り
• ユーザー: fura
• 提出日時: 2026-01-10 16:57:32
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 101 ms / 5,000 ms
• コード長: 7,855 bytes
• コンパイル時間: 4,164 ms
• コンパイル使用メモリ: 362,892 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-01-10 16:57:38
• 合計ジャッジ時間: 5,417 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define impl_overload4(a, b, c, d, e, ...) e
#define impl_overload5(a, b, c, d, e, f, ...) f
#define impl_overload6(a, b, c, d, e, f, g, ...) g
#define impl_overload7(a, b, c, d, e, f, g, h, ...) h

// clang-format off
#define impl_rep4(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define impl_rep3(i, a, b) impl_rep4(i, a, b, 1)
#define impl_rep2(i, n) impl_rep3(i, 0, n)
#define impl_rep1(n) for (int _ = 0; _ < (n); ++_)
#define rep(...) impl_overload4(__VA_ARGS__, impl_rep4, impl_rep3, impl_rep2, impl_rep1)(__VA_ARGS__)

#define impl_rrep4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c))
#define impl_rrep3(i, a, b) impl_rrep4(i, a, b, 1)
#define impl_rrep2(i, n) impl_rrep3(i, 0, n)
#define rrep(...) impl_overload4(__VA_ARGS__, impl_rrep4, impl_rrep3, impl_rrep2)(__VA_ARGS__)
// clang-format on

#define all(v) std::begin(v), std::end(v)

template<typename T>
constexpr int bit(T x, unsigned int k) {
    return (x >> k) & 1;
}

template<typename T>
constexpr bool chmax(T& a, const T& b) {
    return a < b ? a = b, true : false;
}
template<typename T>
constexpr bool chmin(T& a, const T& b) {
    return a > b ? a = b, true : false;
}

void yesno(bool b) {
    std::cout << (b ? "Yes" : "No") << "\n";
}
void yes() {
    yesno(true);
}
void no() {
    yesno(false);
}

struct Setup {
    Setup() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(11);
    }
} setup;

#ifdef LOCAL
#ifndef TEMPLATE_LOCAL_HPP
#define TEMPLATE_LOCAL_HPP

#include "template.hpp"

// clang-format off
#define impl_show1(a) { std::clog << #a << " = " << (a) << endl; }
#define impl_show2(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show1(__VA_ARGS__); }
#define impl_show3(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show2(__VA_ARGS__); }
#define impl_show4(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show3(__VA_ARGS__); }
#define impl_show5(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show4(__VA_ARGS__); }
#define impl_show6(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show5(__VA_ARGS__); }
#define impl_show7(a, ...) { std::clog << #a << " = " << (a) << ", "; impl_show6(__VA_ARGS__); }
#define show(...) { std::clog << "\033[33m"; \
                    impl_overload7(__VA_ARGS__, impl_show7, impl_show6, impl_show5, impl_show4, impl_show3, impl_show2, impl_show1)(__VA_ARGS__) \
                    std::clog << "\033[0m" << std::flush; }
// clang-format on

template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "[";
    bool first = true;
    for (const auto& e: v) {
        if (!first) os << ", ";
        first = false;
        os << e;
    }
    os << "]";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& e: s) {
        if (!first) os << ", ";
        first = false;
        os << e;
    }
    os << "}";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& e: s) {
        if (!first) os << ", ";
        first = false;
        os << e;
    }
    os << "}";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::multiset<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& e: s) {
        if (!first) os << ", ";
        first = false;
        os << e;
    }
    os << "}";
    return os;
}

template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& m) {
    os << "{";
    bool first = true;
    for (const auto& [k, v]: m) {
        if (!first) os << ", ";
        first = false;
        os << k << ": " << v;
    }
    os << "}";
    return os;
}

#endif // TEMPLATE_LOCAL_HPP
#else
#define show(...) ((void)0)
#endif

using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;

using namespace std;

#endif // TEMPLATE_HPP

class mint {
    static const lint MOD = 1234567891;
    lint x;

  public:
    mint(): x(0) {}
    mint(long long y) {
        x = y % MOD;
        if (x < 0) x += MOD;
    }

    mint& operator+=(const mint& m) {
        x += m.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& m) {
        x -= m.x;
        if (x < 0) x += MOD;
        return *this;
    }
    mint& operator*=(const mint& m) {
        x = (long long)x * m.x % MOD;
        return *this;
    }
    mint& operator/=(const mint& m) {
        return *this *= inverse(m);
    }
    mint operator+(const mint& m) const {
        return mint(*this) += m;
    }
    mint operator-(const mint& m) const {
        return mint(*this) -= m;
    }
    mint operator*(const mint& m) const {
        return mint(*this) *= m;
    }
    mint operator/(const mint& m) const {
        return mint(*this) /= m;
    }
    mint operator-() const {
        return -x;
    }

    friend mint inverse(const mint& m) {
        int a = m.x, b = MOD, u = 1, v = 0;
        while (b > 0) {
            int t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return u;
    }

    friend istream& operator>>(istream& is, mint& m) {
        long long t;
        is >> t;
        m = t;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mint& m) {
        return os << m.x;
    }
    int to_int() const {
        return x;
    }
};

mint operator+(long long x, const mint& m) {
    return mint(x) + m;
}
mint operator-(long long x, const mint& m) {
    return mint(x) - m;
}
mint operator*(long long x, const mint& m) {
    return mint(x) * m;
}
mint operator/(long long x, const mint& m) {
    return mint(x) / m;
}

int main() {
    int n;
    lint m;
    cin >> n >> m;
    vector<int> a(n);
    rep (i, n) {
        cin >> a[i];
    }

    // O(NS(log S)(log M)), S = Σ_i A_i
    // a little bit slow, TLE
    /*
    map<lint, mint> dp;
    dp[0] = 1;
    lint b = 1;
    rep (_, 60) {
        rep (i, n) {
            auto tmp = dp;
            for (auto [x, v]: dp) {
                if (m / b + 1 < a[i]) { // avoid overflow
                    continue;
                }
                lint x2 = x + b * a[i];
                if (x2 <= m) {
                    tmp[x2] += v;
                }
            }
            dp = tmp;
        }

        // delete unnecessary keys to improve time complexity
        auto tmp = dp;
        dp.clear();
        for (auto [x, v]: tmp) {
            if (x % b == m % b) {
                dp[x] = v;
            }
        }
        b *= 2;
    }
    cout << dp[m] << endl;
    */

    // more optimized
    // O(NS log M)
    int sum = accumulate(all(a), 0);
    vector<mint> dp(2 * sum + 1);
    dp[0] = 1;
    for (; m > 0; m /= 2) {
        rep (i, n) {
            rrep (x, a[i], 2 * sum + 1) {
                dp[x] += dp[x - a[i]];
            }
        }
        // At this point of t-th iteration (t = 0, 1, ...),
        // dp[x] = (a_1, ..., a_n, 2*a_1, ..., 2*a_n, 2^t*a_1, ..., 2^t*a_n を高々一つずつ使って
        //          x * 2^t + (m % 2^t) を作る場合の数)

        vector<mint> tmp(2 * sum + 1);
        rep (x, 2 * sum + 1) {
            if (x % 2 == m % 2) {
                tmp[x / 2] = dp[x];
            }
        }
        dp = tmp;
    }
    cout << dp[0] << endl;

    return 0;
}