解题思路

下面重点是线性时间统计 bad。

P3496.第3题-好串

1000ms

Difficulty: 6

所属公司 : 饿了么

算法与标签>动态规划

给定长度为 $n$ 的字符串 $s$ ，由字符 $B$ (黑)、 $W$ (白)和 $X$ (未知)组成。你需要将每个 $X$ 替换为 $B$ 或 $W$ ，得到最终字符串。如果最终字符串中存在至少一个连续长度为 $k$ 的子串，该子串全部由字符 $B$ 构成，则称该字符串为好串。

请计算有多少种不同的填充方式，使得得到的字符串为好串,并对结果取模 $10^9+7$ 后输出。

【名词解释】

第一行包含两个整数 $n,k(1 ≦k≦n ≤ 10^6)$ ，分别表示字符串长度、要求的连续黑色长度阈值。

第二行包含一个长度为 $n$ 的字符串 $s$ ，仅由字符 $B、W$ 和 $X$ 组成。

输出一个整数——好串的填充方案总数对 $10^9+7$ 取模后的结果。

输入

3 2
XXX

输出

说明

样例说明：所有 $8$ 种填充中，包含连续" $BB$ "子串的有" $BBW$ "、" $BBB$ ”、" $WBB$ "共3种。

输入

4 3
XXXX

输出

说明

样例说明：长度为 $4$ 的字符串，包含连续" $BBB$ "的填充共有 $3$ 种。

输入

5 2
BWBWB

输出

输入

预期输出（选填）