会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要求我们为包含占位符 ? 的符文序列（由 0/1/? 构成）进行填充，使得最终的完整序列满足：每一个极长同属性段（连续且不能向两端扩展的相同属性符文组成的子串）的长度均为奇数。求所有合法填充方案的总数，结果对 109+7 取模。
由于序列只包含 0 和 1 两种属性，我们可以使用动态规划，从左到右扫描序列，维护当前最后一个极长同属性段的状态。对于当前已经处理的前缀，我们只关心以下两种信息：
- 最后一段的属性是
c（c=0 表示阴，c=1 表示阳），且该段的当前长度为奇数，此时的方案数记为 odd[c]；
- 最后一段的属性是
c，且该段的当前长度为偶数，此时的方案数记为 even[c]。
