結果
問題 | No.1693 Invasion |
ユーザー |
![]() |
提出日時 | 2021-10-01 22:03:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,223 bytes |
コンパイル時間 | 1,772 ms |
コンパイル使用メモリ | 172,188 KB |
実行使用メモリ | 6,104 KB |
最終ジャッジ日時 | 2024-07-19 11:22:14 |
合計ジャッジ時間 | 2,611 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 998244353; using P = pair<int,int>; #define rep(i, n) for(int i = 0; i < n; i++) #define all(x) (x).begin(),(x).end() ll fac[100100], finv[100100], inv[100100]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(int i=2;i<100100;i++){ fac[i] = fac[i-1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD; finv[i] = finv[i-1] * inv[i] % MOD; } } ll COM(int n,int k){ if (n<k) return 0; if (n<0 || k<0) return 0; return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD; } int main(){ int n,m; cin >> n >> m; vector<int> a(n); rep(i,n) cin >> a[i]; sort(all(a)); vector<int> mt(m+1,MOD); mt[0] = 0; rep(i,n){ rep(j,m){ if(mt[j] != MOD){ if(j+a[i] <= m) mt[j+a[i]] = min(mt[j+a[i]],mt[j]+1); } } } //rep(i,m+1) cout << mt[i] << " "; //cout << endl; COMinit(); ll ans = 1; for(int i=1;i<=m;i++){ if(mt[i] == MOD) continue; ans = (ans + COM(m-mt[i], m-i)) % MOD; //cout << ans << endl; } cout << ans << endl; return 0; }