結果

問題 No.3215 Make K types-able
ユーザー jiangxinyang
提出日時 2025-07-25 22:00:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 181 ms / 4,000 ms
コード長 1,842 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 201,192 KB
実行使用メモリ 29,752 KB
最終ジャッジ日時 2025-09-21 11:34:16
合計ジャッジ時間 5,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0