No.2388 At Least K-Characters
タグ : / 解いたユーザー数 78
作問者 : 👑
PCTprobability
amentorimaru
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もしくは右上の雲マークをクリックしてアカウントを作成してください。