D - Avoid K Palindrome Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

A, B, ? からなる N 文字の文字列 S が与えられます。

正整数 K が与えられます。 A, B からなる文字列 T が次の条件を満たすとき、T は良い文字列であるということにします。

  • T の長さ K の連続する部分文字列で、回文であるものが存在しない。

S に含まれる ? の個数を q 個とします。 q 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は 2 ^ q 通りありますが、その中に良い文字列がいくつあるか求めてください。

ただし、答えは非常に大きくなる場合があるので、998244353 で割った余りを求めてください。

制約

  • 2\leq K\leq N\leq 1000
  • K\leq 10
  • S は A, B, ? からなる文字列
  • S の長さは N
  • N,K は整数

入力

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

N K
S

出力

答えを出力せよ。

入力例 1

7 4
AB?A?BA

出力例 1

1

与えられた文字列の中に ? は 2 個あります。 2 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は次の 4 通りあります。

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

このうち、最初の ABAAABA 以外の 3 つの文字列は、長さ 4 の回文 ABBA を連続する部分文字列として含むため、良い文字列ではありません。

よって、1 を出力してください。

入力例 2

40 7
????????????????????????????????????????

出力例 2

116295436

良い文字列の個数を 998244353 で割った余りを求めることに注意してください。

入力例 3

15 5
ABABA??????????

出力例 3

0

? をどのように置き換えても良い文字列にならないこともあります。

入力例 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

出力例 4

259240

Score : 450 points

Problem Statement

You are given a string S of length N consisting of characters A, B, and ?.

You are also given a positive integer K. A string T consisting of A and B is considered a good string if it satisfies the following condition:

  • No contiguous substring of length K in T is a palindrome.

Let q be the number of ? characters in S. There are 2^q strings that can be obtained by replacing each ? in S with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo 998244353.

Constraints

  • 2 \leq K \leq N \leq 1000
  • K \leq 10
  • S is a string consisting of A, B, and ?.
  • The length of S is N.
  • N and K are integers.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.

Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.

Sample Input 2

40 7
????????????????????????????????????????

Sample Output 2

116295436

Ensure to find the number of good strings modulo 998244353.

Sample Input 3

15 5
ABABA??????????

Sample Output 3

0

It is possible that there is no way to replace the ?s to obtain a good string.

Sample Input 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

Sample Output 4

259240