結果
問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
ユーザー |
![]() |
提出日時 | 2021-06-11 22:07:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,550 ms / 4,000 ms |
コード長 | 2,425 bytes |
コンパイル時間 | 2,476 ms |
コンパイル使用メモリ | 207,740 KB |
最終ジャッジ日時 | 2025-01-22 05:56:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int M = 998244353; long long powmod(long long n, long long k) { n %= M; long long res = 1; while (k) { if (k & 1) { res = res * n % M; } k >>= 1; n = n * n % M; } return res; } long long inv(long long n) { return powmod(n, M - 2); } long long binom(long long n, long long r) { if (n < 0 || r < 0 || r > n) return 0; if (n - r < r) r = n - r; long long numer = 1, denom = 1; for (long long i = 0; i < r; ++i) { numer = numer * ((n - i) % M) % M; denom = denom * ((i + 1) % M) % M; } return numer * inv(denom) % M; } long long multi_choose(long long a, long long b) { if (a == 0 && b == 0) { return 1; } else { return binom(a + b - 1, b); } } int main() { cin.tie(0); ios::sync_with_stdio(0); int lim = 3010; long long n; int q; cin >> n >> q; map<long long, int> mp; int sz = 0; int m = min(n, (long long)q); vector<vector<bool>> ok(m, vector<bool>(lim, true)); vector<long long> dp(lim); vector<long long> memo(lim); for (int i = 0; i < lim; ++i) { dp[i] = multi_choose(m, i); memo[i] = multi_choose(n - m, i); } for (int _ = 0; _ < q; ++_) { long long _k; int a, b, s, t; cin >> _k >> a >> b >> s >> t; if (!mp.count(_k)) { mp[_k] = sz; ++sz; } int k = mp[_k]; vector<long long> dp2(lim); for (int i = 0; i < lim; ++i) { long long p = dp[i]; for (int j = 0; j <= i; ++j) { if (ok[k][j]) { p -= dp2[i - j]; } } p = (p % M + M) % M; dp2[i] = p; } for (int i = a; i <= b; ++i) { ok[k][i] = false; } for (int i = 0; i < lim; ++i) { long long p = 0; for (int j = 0; j <= i; ++j) { if (ok[k][j]) { p += dp2[i - j]; } } p %= M; dp[i] = p; } long long ans = 0; for (int i = s; i <= t; ++i) { for (int j = 0; j < lim && j <= i; ++j) { ans = (ans + dp[j] * memo[i - j]) % M; } } cout << ans << '\n'; } return 0; }