atcoder#AGC022E. [AGC022E] Median Replace

[AGC022E] Median Replace

分值:16001600

问题描述

Taichi 认为一个奇数长度 NN 的二进制字符串 XX美丽的,如果可以执行以下操作 N12\frac{N-1}{2} 次,使得最终字符串只包含一个字符 1

  • 选择 XX 的三个连续比特,并将它们替换为它们的中位数。例如,我们可以将 00110 转换为 010,通过对中间三个比特执行操作。

Taichi 有一个字符串 SS,由字符 01? 组成。Taichi 想知道有多少种方法可以将问号替换为 10,使得结果字符串是美丽的,答案取模 109+710^9 + 7

约束条件

  • 1S3000001 \leq |S| \leq 300000
  • S|S| 是奇数。
  • SS 的所有字符要么是 0,要么是 1,要么是 ?

输入

输入通过标准输入提供,格式如下:

SS

输出

打印将问号替换为 01 使得结果字符串是美丽的方式的数量,结果对 109+710^9 + 7 取模。

1??00
2

44 种方法可以替换问号为 01

  • 11100:这个字符串是美丽的,因为我们可以首先对最后 33 位执行操作得到 110,然后对唯一 33 位执行操作得到 1
  • 11000:这个字符串是美丽的,因为我们可以首先对最后 33 位执行操作得到 110,然后对唯一 33 位执行操作得到 1
  • 10100:这个字符串不是美丽的,因为没有序列的操作可以使最终字符串为 1
  • 10000:这个字符串不是美丽的,因为没有序列的操作可以使最终字符串为 1

因此,有 22 种方法可以形成一个美丽的字符串。

?
1

在这种情况下,1 是唯一的美丽字符串。

?0101???10???00?1???????????????0????????????1????0
402589311

记得输出答案对 109+710^9 + 7 取模。