atcoder#AGC022E. [AGC022E] Median Replace
[AGC022E] Median Replace
分值: 分
问题描述
Taichi 认为一个奇数长度 的二进制字符串 是美丽的,如果可以执行以下操作 次,使得最终字符串只包含一个字符 1
:
- 选择 的三个连续比特,并将它们替换为它们的中位数。例如,我们可以将
00110
转换为010
,通过对中间三个比特执行操作。
Taichi 有一个字符串 ,由字符 0
、1
和 ?
组成。Taichi 想知道有多少种方法可以将问号替换为 1
或 0
,使得结果字符串是美丽的,答案取模 。
约束条件
- 是奇数。
- 的所有字符要么是
0
,要么是1
,要么是?
。
输入
输入通过标准输入提供,格式如下:
输出
打印将问号替换为 0
或 1
使得结果字符串是美丽的方式的数量,结果对 取模。
1??00
2
有 种方法可以替换问号为 0
或 1
:
11100
:这个字符串是美丽的,因为我们可以首先对最后 位执行操作得到110
,然后对唯一 位执行操作得到1
。11000
:这个字符串是美丽的,因为我们可以首先对最后 位执行操作得到110
,然后对唯一 位执行操作得到1
。10100
:这个字符串不是美丽的,因为没有序列的操作可以使最终字符串为1
。10000
:这个字符串不是美丽的,因为没有序列的操作可以使最终字符串为1
。
因此,有 种方法可以形成一个美丽的字符串。
?
1
在这种情况下,1
是唯一的美丽字符串。
?0101???10???00?1???????????????0????????????1????0
402589311
记得输出答案对 取模。