問題一覧 > 通常問題

No.2388 At Least K-Characters

レベル : / AI推定難易度 : 1775 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 78
作問者 : 👑 seekworser / テスター : PCTprobability Mizar 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 9113 / 自分の提出
問題文最終更新日: 2023-07-20 17:34:38
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 398 (順位表) の他の問題:

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters. Among the strings of length at most $M$ consisting of lowercase English letters, find the number of strings satisfying the following conditions, and print it modulo $998244353$.

  • It is strictly smaller than $S$ in lexicographical order.
  • At least $K$ distinct characters appear in the string.
What is lexicographical order? (Click to expand)

For $2$ strings $S,T$, we say that $S \le T$ in lexicographical order if and only if one of the following conditions holds.

  • $|S| \le |T|$ and $S$ coincides with the substring of $T$ from the $1$-st character to the $|S|$-th character.
  • There exists $1 \le k \le \min (|S|,|T|)$ such that for $1 \le i \le k−1$, the $i$-th characters of $S$ and $T$ are equal, and the $k$-th character of $S$ is strictly smaller than the $k$-th character of $T$ in alphabetical order.

When $S \le T$ and $S \neq T$, we say that $S$ is strictly smaller than $T$ in lexicographical order ( $S \lt T$ ).

Input

$N \ M \ K$
$S$

  • $1 \le N \le M \le 5 \times 10^5$
  • $1 \le K \le 26$
  • $N,M,K$ are integers.
  • $S$ is a string of length $N$ consisting of lowercase English letters.

Output

Print the number of strings satisfying the conditions, modulo $998244353$.

Sample

Sample 1
Input
1 1 1
d
Output
3

The strings satisfying the conditions are the 3 strings a,b,c. Note that d is not smaller than $S$ in lexicographical order (it is equal).

Sample 2
Input
2 3 2
ac
Output
52
Sample 3
Input
41 100 21
elpqfjecwwkdnslfwbkxlsudppmbqrgjzujshuakd
Output
359048862

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