解题思路

1) 反向计数：总方案 − 坏方案

• 记 X 的个数为 cntX，总方案数：$2^{\text{cntX}}$。
• “坏方案”定义：最终串 没有 连续 $k$ 个 B。
• 于是答案 = $2^{\text{cntX}} - \text{bad}$ (取模)。

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

题目内容

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

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

【名词解释】

• 子串为从原字符串中，连续的选择一段字符(可以全选、可以不选)得到的新字符串。