結果

問題 No.137 貯金箱の焦り
ユーザー ninoinuininoinui
提出日時 2020-11-25 05:26:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 230 ms / 5,000 ms
コード長 4,337 bytes
コンパイル時間 2,210 ms
コンパイル使用メモリ 205,812 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-10-01 01:37:31
合計ジャッジ時間 5,261 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 230 ms
4,380 KB
testcase_13 AC 32 ms
4,376 KB
testcase_14 AC 225 ms
4,376 KB
testcase_15 AC 172 ms
4,380 KB
testcase_16 AC 177 ms
4,376 KB
testcase_17 AC 63 ms
4,380 KB
testcase_18 AC 159 ms
4,380 KB
testcase_19 AC 219 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 94 ms
4,380 KB
testcase_22 AC 11 ms
4,380 KB
testcase_23 AC 9 ms
4,380 KB
testcase_24 AC 48 ms
4,380 KB
testcase_25 AC 133 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <typename T, typename U> bool cmin(T &a, U b) { return a > b && (a = b, true); }
template <typename T, typename U> bool cmax(T &a, U b) { return a < b && (a = b, true); }

template <unsigned int mod> class modint {
private:
  unsigned int v;
  static unsigned int norm(const unsigned int& x) { return x < mod ? x : x - mod; }
  static modint make(const unsigned int& x) {
    modint m;
    return m.v = x, m;
  }
  static modint inv(const modint& x) { return make(inverse(x.v, mod)); }
  static unsigned int inverse(int a, int m) {
    int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;
    while (*v) {
      t = *u / *v;
      swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]);
    }
    return (u[1] % m + m) % m;
  }

public:
  modint() : v{0} {}
  modint(const long val) : v{norm(val % mod + mod)} {}
  modint(const modint<mod>& n) : v{n()} {}
  explicit operator bool() const noexcept { return v != 0; }
  bool operator!() const noexcept { return !static_cast<bool>(*this); }
  modint& operator=(const modint& n) { return v = n(), (*this); }
  modint& operator=(const long val) { return v = norm(val % mod + mod), (*this); }
  modint operator+() const { return *this; }
  modint operator-() const { return v == 0 ? make(0) : make(mod - v); }
  modint operator+(const modint& val) const { return make(norm(v + val())); }
  modint operator-(const modint& val) const { return make(norm(v + mod - val())); }
  modint operator*(const modint& val) const { return make((long)v * val() % mod); }
  modint operator/(const modint& val) const { return *this * inv(val); }
  modint& operator+=(const modint& val) { return *this = *this + val; }
  modint& operator-=(const modint& val) { return *this = *this - val; }
  modint& operator*=(const modint& val) { return *this = *this * val; }
  modint& operator/=(const modint& val) { return *this = *this / val; }
  modint operator+(const long val) const { return modint{v + val}; }
  modint operator-(const long val) const { return modint{v - val}; }
  modint operator*(const long val) const { return modint{(long)(v * (val % mod))}; }
  modint operator/(const long val) const { return modint{(long)v * inv(val)}; }
  modint& operator+=(const long val) { return *this = *this + val; }
  modint& operator-=(const long val) { return *this = *this - val; }
  modint& operator*=(const long val) { return *this = *this * val; }
  modint& operator/=(const long val) { return *this = *this / val; }
  bool operator==(const modint& val) const { return v == val.v; }
  bool operator!=(const modint& val) const { return !(*this == val); }
  bool operator==(const long val) const { return v == norm(val % mod + mod); }
  bool operator!=(const long val) const { return !(*this == val); }
  unsigned int operator()() const { return v; }
  friend modint operator+(const long val, const modint& n) { return n + val; }
  friend modint operator-(const long val, const modint& n) { return modint{val - n()}; }
  friend modint operator*(const long val, const modint& n) { return n * val; }
  friend modint operator/(const long val, const modint& n) { return modint{val} / n; }
  friend bool operator==(const long val, const modint& n) { return n == val; }
  friend bool operator!=(const long val, const modint& n) { return !(val == n); }
  friend istream& operator>>(istream& is, modint& n) {
    unsigned int v;
    return is >> v, n = v, is;
  }
  friend ostream& operator<<(ostream& os, const modint& n) { return (os << n()); }
  friend modint mod_pow(modint x, long n) {
    modint ans = 1;
    while (n) {
      if (n & 1) ans *= x;
      x *= x, n >>= 1;
    }
    return ans;
  }
};

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  using mint = modint<1234567891>;

  int N;
  long M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);

  int MX = N * *max_element(A.begin(), A.end()) * 2 + 1;
  vector<mint> DP(MX);
  DP.at(0) = 1;
  while (M) {
    for (auto a : A) {
      for (int i = MX - 1; i >= 0; i--) {
        if (i - a >= 0) DP.at(i) += DP.at(i - a);
      }
    }
    vector<mint> next(MX);
    for (int i = 0; i < MX; i++) {
      if ((i & 1) == (M & 1)) next.at(i >> 1) = DP.at(i);
    }
    DP = next;
    M /= 2;
  }
  cout << DP.front() << "\n";
}
0