結果

問題 No.2388 At Least K-Characters
コンテスト
ユーザー norioc
提出日時 2026-01-08 18:23:18
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,531 ms / 4,000 ms
コード長 2,380 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,182 ms
コンパイル使用メモリ 352,144 KB
実行使用メモリ 12,020 KB
最終ジャッジ日時 2026-01-08 18:23:55
合計ジャッジ時間 34,665 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353;

int N, M, K;
string S;
vector<int> cs;
vector<pair<int, int>> kinds;
long long ans = 0;

inline long long op(long long a, long long b) {
    return (a + b) % MOD;
}

void digit_dp() {
    unordered_map<long long, long long> dp, pp;
    auto encode = [](int m, bool lt) {
        return (long long)m << 1 | (lt ? 1LL : 0LL);
    };
    auto decode = [](long long key) {
        return make_pair((int)(key >> 1), (bool)(key & 1));
    };

    dp[encode(0, false)] = 1;

    for (int x = 0; x < M; ++x) {
        pp.clear();
        dp.swap(pp);

        for (auto &it : pp) {
            long long key = it.first;
            long long v = it.second;
            auto [m, lt] = decode(key);
            int p = x;

            if (lt) {
                if (m > 0) {
                    dp[encode(m, true)] = op(dp[encode(m, true)], v * m % MOD);
                    if (m >= K) ans = (ans + v * m) % MOD;
                }
                if (m < 26) {
                    dp[encode(m + 1, true)] =
                        op(dp[encode(m + 1, true)], v * (26 - m) % MOD);
                    if (m + 1 >= K) ans = (ans + v * (26 - m)) % MOD;
                }
            } else if (p < N) {
                for (int i = 0; i < cs[p]; ++i) {
                    int nm, b;
                    if (p == 0) {
                        nm = 0;
                        b = 0;
                    } else {
                        nm = kinds[p - 1].first;
                        b = kinds[p - 1].second;
                    }
                    if (!(b & (1 << i))) nm++;
                    dp[encode(nm, true)] = op(dp[encode(nm, true)], v);
                    if (nm >= K) ans = (ans + v) % MOD;
                }
                if (p + 1 < N && kinds[p].first >= K) {
                    ans = (ans + 1) % MOD;
                }
                dp[encode(0, false)] = op(dp[encode(0, false)], v);
            }
        }
    }
}

int main() {
    cin >> N >> M >> K;
    cin >> S;

    cs.resize(N);
    for (int i = 0; i < N; ++i) cs[i] = S[i] - 'a';

    set<char> st;
    int b = 0;
    for (int i = 0; i < N; ++i) {
        st.insert(S[i]);
        b |= 1 << (S[i] - 'a');
        kinds.emplace_back((int)st.size(), b);
    }

    digit_dp();
    cout << ans % MOD << '\n';
    return 0;
}
0