1000ms

Difficulty: 6

所属公司 : 饿了么

时间 :2025年8月29日(算法方向)

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

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$ 后输出。

【名词解释】

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