結果

問題 No.2388 At Least K-Characters
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-07-21 22:14:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,416 bytes
コンパイル時間 2,081 ms
コンパイル使用メモリ 202,548 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-05 03:43:53
合計ジャッジ時間 5,385 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll const m = 998244353;
ll kai[30], fkai[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 <= K) {
		return mpow(26, al);
	} 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;
				kj = (kj * mpow(26 - n + k - i, al)) % m;
				if (i & 1) {
					ret = (m + ret - kj) % m;
				} else {
					ret = (ret + kj ) % m;
				}
			}
		}
		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;
	}
	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);
			ans += (p * (x - cnt - 1) + q * (cnt)) % m;
			ans %= m;
		}
		nm -= !did[x];
		did[x] = true;
	}
	cout << ans << endl;
}
0