题目描述
有一个$1$维的扫雷游戏，每个格子用$*$表示有雷，用$0/1/2$表示无雷并且相邻格子中有$0/1/2$个雷。
给定一个仅包含$?$、$*$、$0$、$1$、$2$的字符串$s$，问有多少种方法将所有的$?$改为$*/0/1/2$使其合法。
输入格式
一行一个字符$s$。
输出格式
一行一个整数表示答案，对${10}^9+7$取模。
样例
样例输入：
?1?
样例输出：
2
数据范围与提示
对于$30\%$的数据，$|S|leqslant 20$。
对于$60\%$的数据，$|S|leqslant 1,000$。
对于$100\%$的数据，$|S|leqslant {10}^6$。
题解
显然数据范围只允许我们$Theta(n)$求解，那么也只能考虑$DP$了。
设$dp[i][j]$表示到了$i$位置，当前选了$j$，$j$分为五种情况，如下：
$alpha.$当前位置没有雷。
$eta.$当前位置左边有一个雷。
$gamma.$当前位置旁边有两个雷。
$delta.$当前位置有雷。
$epsilon.$当前位置左边有雷。
为方便，以上五种情况下面均以数字$0sim 5$代替。
那么现在来考虑转移，首先是第一个位置，分为四种情况：
$alpha.$无雷：$dp[1][0]=1$。
$eta.$旁边有一个雷：$dp[1][4]=1$。
$gamma.$本身有雷：$dp[1][3]=1$.
$delta.$为$?$：$dp[1][0]=dp[1][3]=dp[1][4]=1$（第一个位置不可能出现$1,2$两种情况）。
那么我们在来考虑过程中的转移，依然分类讨论（注意以下''中为题目中给出的棋盘的状态，而不是我上面列出的对于五种情况的编号）：
$alpha.'0':$可以由$0,1$两种情况转移得来，即为：$dp[i][0]=dp[i-1][0]+dp[i-1][1]$。
$eta.'1':$则还分两种情况，分别是$1$和$4$，那么式子为：$dp[i][1]=dp[i-1][3]$和$dp[i][4]=dp[i-1][0]+dp[i-1][1]$。
$gamma.'2':$只能由$3$转移得来，即：$dp[i][2]=dp[i-1][3]$。
$delta.'*':$可以由$2,3,4$三种情况转移得来，即：$dp[i][3]=dp[i-1][2]+dp[i-1][3]+dp[i-1][4]$。
$epsilon.'?'$包含以上所有情况。
最后来考虑如何统计答案，因为最后一位不可能是$2$和$4$两种情况，所以答案即为：$dp[n][0]+dp[n][1]+dp[n][3]$。
时间复杂度：$Theta(n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
char ch[1000001];
long long dp[1000001][5];
int main()
{
scanf("%s",ch+1);
int n=strlen(ch+1);
switch(ch[1])
{
case '0':dp[1][0]=1;break;
case '1':dp[1][4]=1;break;
case '*':dp[1][3]=1;break;
case '?':dp[1][0]=dp[1][4]=dp[1][3]=1;break;
}
for(int i=2;i<=n;i++)
switch(ch[i])
{
case '0':dp[i][0]=(dp[i-1][0]+dp[i-1][1])%1000000007;break;
case '1':dp[i][1]=dp[i-1][3];dp[i][4]=(dp[i-1][0]+dp[i-1][1])%1000000007;break;
case '2':dp[i][2]=dp[i-1][3];break;
case '*':dp[i][3]=(dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%1000000007;break;
case '?':
dp[i][0]=(dp[i-1][0]+dp[i-1][1])%1000000007;
dp[i][1]=dp[i-1][3];
dp[i][3]=(dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%1000000007;
dp[i][4]=(dp[i-1][0]+dp[i-1][1])%1000000007;
dp[i][2]=dp[i-1][3];
break;
}
printf("%lld",(dp[n][0]+dp[n][1]+dp[n][3])%1000000007);
return 0;
}
rp++