結果
問題 | No.1693 Invasion |
ユーザー |
![]() |
提出日時 | 2021-10-01 21:55:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 2,232 bytes |
コンパイル時間 | 2,256 ms |
コンパイル使用メモリ | 206,000 KB |
最終ジャッジ日時 | 2025-01-24 19:07:18 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; //using mint = modint1000000007; using ll = long long; using ld = long double; using pll = pair<ll, ll>; using tlll = tuple<ll, ll, ll>; constexpr ll INF = 1LL << 60; template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;} template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;} ll safemod(ll A, ll M) {return (A % M + M) % M;} ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;} ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);} #define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false) class mintcombination { public: vector<mint> fac, finv, inv; mintcombination(ll M) { fac.resize(M + 1); finv.resize(M + 1); inv.resize(M + 1); fac.at(0) = 1, finv.at(0) = 1; fac.at(1) = 1, finv.at(1) = 1, inv.at(1) = 1; for (ll i = 2; i <= M; i++) { fac.at(i) = fac.at(i - 1) * i; inv.at(i) = mint::mod() - inv.at(mint::mod() % i) * (mint::mod() / i); finv.at(i) = finv.at(i - 1) * inv.at(i); } } mint P(ll N, ll K) { if (N < K) return 0; if (N < 0 || K < 0) return 0; return fac.at(N) * finv.at(N - K); } mint C(ll N, ll K) { if (N < K) return 0; if (N < 0 || K < 0) return 0; return fac.at(N) * finv.at(K) * finv.at(N - K); } mint H(ll N, ll K) { return C(N + K - 1, K); } }; int main() { ll N, M; cin >> N >> M; vector<ll> A(N); for (ll i = 0; i < N; i++) { cin >> A.at(i); } vector dp(N + 1, vector(M + 1, INF)); for (ll i = 0; i < N + 1; i++) { dp.at(i).at(0) = 0; } for (ll i = 0; i < N; i++) { for (ll j = 0; j <= M; j++) { if (j < A.at(i)) dp.at(i + 1).at(j) = dp.at(i).at(j); else dp.at(i + 1).at(j) = min(dp.at(i + 1).at(j - A.at(i)) + 1, dp.at(i).at(j)); } } mintcombination com(M + 10); mint ans = 0; for (ll j = 0; j <= M; j++) { ll k = dp.at(N).at(j); mint tmp = com.C(M - k, j - k); ans += tmp; } cout << ans.val() << endl; }