解题思路

反向计数
记 X 的个数为 $\mathrm{cntX}$ ，总填充方案数为 $2^{\mathrm{cntX}}$ 。定义“不达标”为最终串中没有连续 $k$ 个 B。答案为 $2^{\mathrm{cntX}} - \mathrm{bad}$ （取模）。
线性 DP 统计不达标方案
记 okB[i]：第 $i$ 位可以是 B（即 $s_i \ne$ W）；okW[i]：第 $i$ 位可以是 W（即 $s_i \ne$ B）。Wpre[i] 为前 $i$ 位中 W 的个数。
- $dp[i]$ ：前 $i$ 位且不含连续 $k$ 个 B 的方案数；

题目描述

工程师林沐正在配置一条由 $n$ 个指示灯组成的灯带。

每个位置的指示灯有两种颜色：

当前灯带中还有一些位置尚未确定颜色，用字符 X 表示。对于每一个 X，都可以独立地将其设置为 B 或 W。