题目描述

帕秋莉掌握了一种火属性魔法
由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内
现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种
对于一个格子，里面会有以下几种字符：
0：这个格子没有烈焰，且其左右两个格子均没有烈焰
1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰
2：这个格子没有烈焰，且其左右两个格子中均有烈焰
*：这个格子有烈焰
？：未告诉你本格情况

题解

很明显是一道dp的题目，我们考虑它的转移方程是怎么样的。由题目里的限制 可以得到，当前位置是否为烈焰与他前一位和后一位是否为烈焰都有关，并且当我们枚举到当前位置的时候前一位的前一位是没有用的，
所以我们设dp[i][j 0/1][k 0/1]表示当前在i为状态为j,i+1位的状态为k。所以dp[][][]转移方程就可以轻松的得到啦~
并且由于第0位，第n+1位都不可能为烈焰，所以我们在初始化和最后统计答案的时候要注意一下下

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f;
const int mod  = 1e9 + 7;
const int maxn = 2e6 + 6;
const int N    = 1e3 + 4;
const double eps = 1e-6;
ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}

char s[maxn];
int n;
ll ans,dp[maxn][2][2];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    dp[0][0][0]=dp[0][0][1]=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
            dp[i][0][0]=dp[i-1][0][0];
        }
        if(s[i]=='1'){
            dp[i][0][1]=dp[i-1][0][0];
            dp[i][0][0]=dp[i-1][1][0];
        }
        if(s[i]=='2'){
            dp[i][0][1]=dp[i-1][1][0];

        }
        if(s[i]=='*'){
            dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
            dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
        }
        if(s[i]=='?'){
            dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%mod;
            dp[i][0][1]=(dp[i-1][1][0]+dp[i-1][0][0])%mod;
            dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
            dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
        }
    }
    printf("%lld\n",dp[n][0][0]+dp[n][1][0]);
}