F - ARC Stamp

Contest Duration: 2021-12-05(Sun) 12:00 - 2021-12-05(Sun) 14:00 (local time) (120 minutes) Back to Home

F - ARC Stamp Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $1000$ 点

問題文

A, R, C からなる文字列 $S$ から始めて、「連続する三文字を選んで ARC に上書きする」操作を $K$ 回以下行ったところ、文字列 $T$ が得られました。

さて、最初の文字列 $S$ として何通りがあり得るでしょうか？これを $998244353$ で割った余りを求めてください。

制約

$3 \leq |T| \leq 5000$
$0 \leq K \leq 10000$
$T$ は A, R, C からなる文字列

入力

入力は以下の形式で標準入力から与えられます。

 $T$ 
 $K$

出力

答えを出力してください。

入力例 1Copy

Copy

ARCCARC
1

出力例 1Copy

Copy

例えば、最初の文字列 $S$ が次のようなとき、 $1$ 回以下の操作で文字列 $T$ = ARCCARC を得ることができます。

$S$ = ARCCARC のとき：操作を行わないでも文字列 ARCCARC が得られる．
$S$ = CRACARC のとき： $S$ の $1, 2, 3$ 文字目を選んで ARC に上書きすると、文字列 ARCCARC が得られる。
$S$ = ARCCCCC のとき： $S$ の $5, 6, 7$ 文字目を選んで ARC に上書きすると、文字列 ARCCARC が得られる。

上に挙げたもの以外にもたくさんあり、 $S$ としてあり得るものは全部で $53$ 通りです。

入力例 2Copy

Copy

ARARCRCA
5

出力例 2Copy

Copy

最初の文字列 $S$ が AAAAAAAA のとき、例えば次のような $5$ 回以下の操作で文字列 $T$ = ARARCRCA を得ることができます。

ステップ $1$ ：まず、 $3, 4, 5$ 文字目を選んで ARC に上書きすると、文字列 AAARCAAA が得られる。
ステップ $2$ ：次に、 $5, 6, 7$ 文字目を選んで ARC に上書きすると、文字列 AAARARCA が得られる。
ステップ $3$ ：次に、 $1, 2, 3$ 文字目を選んで ARC に上書きすると、文字列 ARCRARCA が得られる。
ステップ $4$ ：最後、 $3, 4, 5$ 文字目を選んで ARC に上書きすると、文字列 ARARCRCA が得られる。

それ以外にも $S$ としてあり得るものはたくさんあり、全部で $2187$ 通りです。

入力例 3Copy

Copy

AARCRRARCC
0

出力例 3Copy

Copy

$0$ 回の操作で文字列 $T$ = AARCRRARCC を得られるのは、最初の時点で $S = T$ のとき、すなわち $S$ = AARCRRARCC の $1$ 通りしかありません。

入力例 4Copy

Copy

AAAAARRRRRCCCCC
131

出力例 4Copy

Copy

この入力例では、 $S$ としてあり得るものは AAAAARRRRRCCCCC の $1$ 通りだけです。

入力例 5Copy

Copy

CAARCACRAAARARARCRCRARCARARCRRARC
9

出力例 5Copy

Copy

797833187

最初の文字列 $S$ としてあり得るものは $320236026147$ 通りあるので、これを $998244353$ で割った余りである $797833187$ を出力してください。

Score : $1000$ points

Problem Statement

On a string $S$ consisting of A, R, and C, we did the following operation at most $K$ times: choose three consecutive characters and overwrite them with ARC. The result is the string $T$ .

How many strings are there that could be the initial string $S$ ? Find this count modulo $998244353$ .

Constraints

$3 \leq |T| \leq 5000$
$0 \leq K \leq 10000$
$T$ is a string consisting of A, R, and C.

Input

Input is given from Standard Input in the following format:

 $T$ 
 $K$

Output

Print the answer.

Sample Input 1Copy

Copy

ARCCARC
1

Sample Output 1Copy

Copy

Below are some examples of the initial string $S$ from which we can get the string $T$ = ARCCARC with at most $1$ operation.

$S$ = ARCCARC: we can choose to do nothing to get ARCCARC.
$S$ = CRACARC: we can choose the $1$ -st, $2$ -nd, $3$ -rd characters and overwrite them with ARC to get ARCCARC.
$S$ = ARCCCCC: we can choose the $5$ -th, $6$ -th, $7$ -th characters and overwrite them with ARC to get ARCCARC.

There are many other strings that could be $S$ , for a total of $53$ .

Sample Input 2Copy

Copy

ARARCRCA
5

Sample Output 2Copy

Copy

If the intial string $S$ is AAAAAAAA, one way to get $T$ = ARARCRCA with at most $5$ operations is as follows.

Step $1$ : choose the $3$ -rd, $4$ -th, $5$ -th characters and overwrite them with ARC to get the string AAARCAAA.
Step $2$ : choose the $5$ -th, $6$ -th, $7$ -th characters and overwrite them with ARC to get the string AAARARCA.
Step $3$ : choose the $1$ -st, $2$ -nd, $3$ -rd characters and overwrite them with ARC to get the string ARCRARCA.
Step $4$ : choose the $3$ -rd, $4$ -th, $5$ -th characters and overwrite them with ARC to get the string ARARCRCA.

There are many other strings that could be $S$ , for a total of $2187$ .

Sample Input 3Copy

Copy

AARCRRARCC
0

Sample Output 3Copy

Copy

We can get $T$ = AARCRRARCC with $0$ operations in only one case in which $S = T$ from the beginning, or $S$ = AARCRRARCC.

Sample Input 4Copy

Copy

AAAAARRRRRCCCCC
131

Sample Output 4Copy

Copy

In this case, there is just one string that could be $S$ : AAAAARRRRRCCCCC.

Sample Input 5Copy

Copy

CAARCACRAAARARARCRCRARCARARCRRARC
9

Sample Output 5Copy

Copy

797833187

There are $320236026147$ strings that could be $S$ , so print this count modulo $998244353$ , which is $797833187$ .