問題一覧 > 通常問題

No.2388 At Least K-Characters

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

問題文

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

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

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

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

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

入力

N M KN \ M \ K
SS

  • 1≤N≤M≤5×1051 \le N \le M \le 5 \times 10^5
  • 1≤K≤261 \le K \le 26
  • N,M,KN,M,K は整数
  • SS は英小文字からなる長さ NN の文字列

出力

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

サンプル

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

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

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

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