問題一覧 > 通常問題

No.2388 At Least K-Characters

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 77
作問者 : 👑 seekworserseekworser / テスター : 👑 PCTprobabilityPCTprobability 👑 MizarMizar 👑 amentorimaruamentorimaru
5 ProblemId : 9113 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-20 17:34:38

問題文

英小文字からなる長さ $N$ の文字列 $S$ が与えられます。 英小文字からなる長さ $M$ 以下の文字列であって以下の条件を満たす文字列の個数を、 $998244353$ で割ったあまりを出力してください。

  • 辞書順で $S$ よりも真に小さい
  • 文字列中に $K$ 種類以上の文字が出現する
辞書順とは？（クリックで開く）

$2$ つの文字列 $S,T$ が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で $S \le T$ であると言います。

  • $|S| \le |T|$ かつ $S$ は $T$ の $1$ 番目から $|S|$ 番目までの部分文字列と一致する。
  • $1 \le k \le \min (|S|,|T|)$ が存在し、 $1 \le i \le k−1$ について、 $S$ と $T$ の $i$ 文字目は等しく、 $S$ の $k$ 文字目は $T$ の $k$ 文字目よりアルファベット順で真に小さい。

$S \le T$ かつ $S \neq T$ のとき、 $S$ は $T$ よりも辞書順で真に小さい（ $S \lt T$ ）と言います。

入力

$N \ M \ K$
$S$

  • $1 \le N \le M \le 5 \times 10^5$
  • $1 \le K \le 26$
  • $N,M,K$ は整数
  • $S$ は英小文字からなる長さ $N$ の文字列

出力

条件を満たす文字列の個数を $998244353$ で割った余りを出力せよ。

サンプル

サンプル1
入力
1 1 1
d
出力
3

条件を満たす文字列は a,b,c の3種類です。 d は辞書順で $S$ よりも小さくない（等しい）ことに注意してください。

サンプル2
入力
2 3 2
ac
出力
52
サンプル3
入力
41 100 21
elpqfjecwwkdnslfwbkxlsudppmbqrgjzujshuakd
出力
359048862

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。