結果
問題 | No.1693 Invasion |
ユーザー | ktr216 |
提出日時 | 2021-10-01 22:15:08 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 1,374 bytes |
コンパイル時間 | 1,669 ms |
コンパイル使用メモリ | 175,904 KB |
実行使用メモリ | 4,916 KB |
最終ジャッジ日時 | 2023-09-26 17:38:47 |
合計ジャッジ時間 | 3,682 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,376 KB |
testcase_07 | AC | 3 ms
4,376 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 78 ms
4,468 KB |
testcase_10 | AC | 55 ms
4,384 KB |
testcase_11 | AC | 37 ms
4,376 KB |
testcase_12 | AC | 92 ms
4,380 KB |
testcase_13 | AC | 32 ms
4,380 KB |
testcase_14 | AC | 35 ms
4,376 KB |
testcase_15 | AC | 24 ms
4,380 KB |
testcase_16 | AC | 56 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 107 ms
4,792 KB |
testcase_19 | AC | 4 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 119 ms
4,768 KB |
testcase_22 | AC | 138 ms
4,916 KB |
testcase_23 | AC | 126 ms
4,560 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, l, r) for (int i = (l); i < (r); i++) using namespace std; typedef long long ll; ll MOD = 998244353; vector<ll> f(1e5 + 1, 1); ll mod_pow(ll x, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } ll C(ll n, ll k) { ll ret = f[n] * mod_pow(f[k], MOD - 2, MOD) % MOD; ret = ret * mod_pow(f[n - k], MOD -2, MOD) % MOD; return ret; } int main() { ll ans = 0; int N, M; cin >> N >> M; rep(i, 0, M) f[i + 1] = f[i] * (i + 1) % MOD; vector<int> A(N); rep(i, 0, N) cin >> A[i]; queue<pair<int, int>> q; vector<int> b(M + 1, 1e9); //x個選ぶのに最小でb(x)回必要; q.push(make_pair(0, 0)); map<pair<int, int >, bool> done; b[0] = 0; while (!q.empty()) { int x = q.front().first, y = q.front().second; //cout << "(" << x << "," << y << ")"; q.pop(); rep(i, 0, N) { if (y + A[i] <= M && x + 1 < b[y + A[i]]) { b[y + A[i]] = x + 1; q.push(make_pair(x + 1, y + A[i])); } } } rep(i, 0, M + 1) { //cout << i << " " << b[i] << endl; if (b[i] == 1e9) continue; ans += C(M - b[i], i - b[i]); ans %= MOD; } cout << ans << endl; }