結果
問題 |
No.3215 Make K types-able
|
ユーザー |
|
提出日時 | 2025-07-25 22:00:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 4,000 ms |
コード長 | 1,842 bytes |
コンパイル時間 | 2,262 ms |
コンパイル使用メモリ | 201,056 KB |
実行使用メモリ | 29,804 KB |
最終ジャッジ日時 | 2025-09-04 08:28:08 |
合計ジャッジ時間 | 5,780 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 998244353; const int N = 200005; const int INF = 0x3f3f3f3f; ll powmod(ll x, ll y, ll t = mod) { ll res = 1; x %= t; while (y) { if (y & 1) res = res * x % t; y >>= 1; x = x * x % t; } return res; } ll f[N][15]; int main() { int _; cin >> _; vector<pair<int, int>> qs(_); int maxn = 0, maxk = 0; for (int i = 0; i < _; i++) { int n, k; cin >> n >> k; qs[i] = {n, k}; maxn = max(maxn, n); maxk = max(maxk, k - 1); } if (maxk > 10) maxk = 10; vector<int> pw(maxn + 1, 0); pw[0] = 1; for (int i = 1; i <= maxn; i++) pw[i] = (int)((ll)pw[i - 1] * 2 % (mod - 1)); vector<int> val(maxn + 1, 0); for (int h = 1; h <= maxn; h++) { ll e = pw[h] - 2; if (e < 0) e += mod - 1; val[h] = (int)powmod(2, e, mod); } if (maxk >= 1) f[1][1] = 1; for (int h = 2; h <= maxn; h++) { for (int r = 0; r <= maxk; r++) { ll sum = 0; for (int i = 0; i <= r; i++) { ll A = (i == 0 ? (val[h - 1] + f[h - 1][0]) % mod : f[h - 1][i]); int j = r - i; ll B = (j == 0 ? (val[h - 1] + f[h - 1][0]) % mod : f[h - 1][j]); sum = (sum + A * B) % mod; } f[h][r] = sum; } } for (auto [n, k] : qs) { int r = k - 1; if (r < 0 || r > maxk) { cout << 0 << "\n"; } else if (r >= 1) { cout << f[n][r] << "\n"; } else { ll ans = (f[n][0] + val[n]) % mod; cout << ans << "\n"; } } return 0; }