题解

本题是 codeforces 难度分为 1900分的原题 链接

由于本题是有后效性的动态规划，直接递推比较难写，这边采用记忆化搜索的方法来写

定义 $dfs(i,j)$ 表示考虑 $s[0] ... s[i]$，$j=0/1/2$ ，分别为：$s[i]$ 不能是雷/ $s[i]$ 一定是雷/ $s[i+1]$ 是雷

返回在这种情况下的方案数。

问题描述

小红在研究古代遗留下来的魔法阵时发现了一系列神秘的符号。这些符号代表着不同的魔法能量：未知能量用“？”表示，已爆发的能量用“*”标记。每一个没有能量爆发的符号位置上有一个数字（0 到 2），这个数字表示该位置左右两侧已爆发能量的总数。现在小红想要确定所有可能的已爆发能量分布情况的数量。

输入格式

第一行包含一个字符串，仅包含“*”和“？”以及“0”到“2”的字符，代表当前魔法阵的局面。字符串的长度不超过 100000。

输出格式

输出一个整数，表示所有可能的已爆发能量分布情况的数量。结果可能非常大，因此请输出该数除以 $10^9 + 7$ 的余数。

样例输入

??**2?11??

样例输出

8

评测数据与规模

对于所有评测数据，字符串长度不超过 100000。