結果

問題 No.2388 At Least K-Characters
ユーザー Carpenters-Cat
提出日時 2023-07-21 22:39:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 114 ms / 4,000 ms
コード長 1,885 bytes
コンパイル時間 2,211 ms
コンパイル使用メモリ 195,784 KB
最終ジャッジ日時 2025-02-15 17:10:27
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll const m = 998244353;
ll kai[30], fkai[30], iv[30];
ll mpow(ll a, ll n) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = (ret * a) % m;
        n >>= 1;
        a = (a * a) % m;
    }
    return ret;
}
ll comb(ll n, ll r) {
    if (n < 0 || r < 0 || n < r) return 0;
    return (((kai[n] * fkai[r]) % m) * fkai[n - r]) % m;
}
ll calc(ll n, ll K, ll al) {
    if (n < 0) return 0;
    if (n <= K) {
        ll r = mpow(26, al + 1) - 1;
        r = (r * iv[25])%m;
        return r;
    } else {
        ll ret = 0;
        for (int k = n - K; k <= n; k ++) {
            for (int i = 0; i <= k; i ++) {
                ll kj = comb(n, k) * comb(k, i);
                kj %= m;
                int pk = 26 - n + k - i;
                if (pk > 1) {
                    ll q = mpow(pk, al + 1) - 1;
                    q = (q * iv[pk - 1]) % m;
                    kj = (kj * q) % m;
                } else if (pk) {
                    ll q = al + 1;
                    kj = (kj * q) % m;
                } else {
                    kj = 0;
                }
                if (i & 1) {
                    ret = (m + ret - kj) % m;
                } else {
                    ret = (ret + kj) % m;
                }
            }
            // cout << ret << endl;
        }
        return ret;
    }
}
int main () {
    int N, M, K;
    cin >> N >> M >> K;
    K = 26 - K;
    string s;
    cin >> s;
    kai[0] = 1;
    for (int i = 1; i <= 27; i ++) {
        kai[i] = (kai[i - 1] * i) % m;
    }
    fkai[27] = mpow(kai[27], m - 2);
    for (int i = 27; i > 0; i --) {
        fkai[i - 1] = (fkai[i] * i) % m;
    }
    iv[0] = 0;
    for (int i = 1; i < 28;i ++) {
        iv[i] = kai[i - 1] * fkai[i];
        iv[i] %= m;
    }
    bool did[30];
    fill(did, did + 30, false);
    int nm = 26;
    ll ans = 0;
    for (int i = 0; i < N; i ++) {
        int x = s[i] - 'a';
        if (s[i] > 'a') {
            int cnt = x;
            for (int j = 0; j < x; j ++) cnt -= did[j];
            ll p = calc(nm, K, M - i - 1), q = calc(nm - 1, K, M - i - 1);
            // cout << p << " " << q << endl;
            ans += (p * (x - cnt) + q * (cnt)) % m;
            ans %= m;
        }
        nm -= !did[x];
        did[x] = true;
        if (nm <= K && i < N - 1) {
            ans = (ans + 1) % m;
        }
    }
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0