結果

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

ソースコード

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