結果

問題 No.2388 At Least K-Characters
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-07-21 22:39:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 120 ms / 4,000 ms
コード長 1,885 bytes
コンパイル時間 2,006 ms
コンパイル使用メモリ 203,964 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-05 03:51:20
合計ジャッジ時間 4,810 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 119 ms
6,944 KB
testcase_17 AC 67 ms
6,940 KB
testcase_18 AC 120 ms
6,940 KB
testcase_19 AC 74 ms
6,940 KB
testcase_20 AC 74 ms
6,944 KB
testcase_21 AC 73 ms
6,944 KB
testcase_22 AC 73 ms
6,944 KB
testcase_23 AC 72 ms
6,944 KB
testcase_24 AC 73 ms
6,940 KB
testcase_25 AC 71 ms
6,944 KB
testcase_26 AC 74 ms
6,940 KB
testcase_27 AC 73 ms
6,944 KB
testcase_28 AC 73 ms
6,944 KB
testcase_29 AC 74 ms
6,940 KB
testcase_30 AC 74 ms
6,940 KB
testcase_31 AC 74 ms
6,940 KB
testcase_32 AC 74 ms
6,940 KB
testcase_33 AC 73 ms
6,940 KB
testcase_34 AC 74 ms
6,940 KB
testcase_35 AC 71 ms
6,940 KB
testcase_36 AC 72 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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