D - X-word Database
Ceylon
2
s
1024
MB
100
点
問題文
小文字アルファベットからなる文字列 $T$ が次の2つの条件を共に満たすとき、その文字列をよい文字列と呼びます。
- $T$ の長さは $X$ 以下
- 連続する部分列に
cyanを含む
文字列 $S$ が与えられます。辞書順で $S$ 以下の文字列であり、よい文字列となるようなものは何個存在しますか？
ただし、答えが非常に大きくなることがあるので$998244353$で割った余りを求めてください。
文字列の辞書順とは？
文字列 $A = A_1A_2\cdots A_{|A|}$ が文字列 $B = B_1B_2\cdots B_{|B|}$ より辞書順で小さいとは、以下の $2$ つのうちどちらかが成り立つ場合にいいます。ここで、 $|A|, |B|$ はそれぞれ $A, B$ の文字列の長さを表します。
- $|A| < |B|$ かつ $A_1A_2\cdots A_{|A|} = B_1B_2\cdots B_{|A|}$ である。
- ある整数 $1 \leq i \leq \min(|A|, |B|)$ が存在して、以下の $2$ つが成り立つ。
- $A_1A_2\cdots A_{i-1} = B_1B_2\cdots B_{i-1}$
- $A_i$ のほうが、アルファベット順で $B_i$ より前
制約
制約
- $4 \leq X \leq 10^5, X$ は整数
- $1 \leq |S| \leq X$
- $S$ は小文字アルファベットからなる文字列
部分点
以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。
- (20点) $X \leq 8$
- (40点) $X \leq 10^3, S$ は
zのみからなる長さ $X$ の文字列 - (40点) 追加の制約なし
部分点2 のみ に正解し、部分点1に正解しないコードを提出した場合、得点は40点となることに注意。
入力
入力は、以下の形式で標準入力から与えられる。
$X$
$S$
出力
答えを $998244353$ で割ったあまりを1行で出力せよ。
入力例 1
5
cyanc
出力例 1
7
よい文字列は、
acyanbcyanccyancyancyanacyanbcyanc
の $7$ つです。
このサンプルは部分点1の制約を満たします。
入力例 2
8
database
出力例 2
694119
このサンプルは部分点1の制約を満たします。
入力例 3
10
zzzzzzzzzz
出力例 3
239563112
このサンプルは部分点2の制約を満たします。
入力例 4
1599
graybrowngreencyan
出力例 4
433406175