solution

一开始考虑用表示前i个位置,第个位置有(1)没有(0)烈焰,的方案数。发现不好转移。

当一种状态无法转移时,就再加一维状态

表示前i个位置,第i个位置的状态为j,第个位置状态为的方案数。

然后就可以转移了。

当第个位置的信息为时,就有

当第个位置的信息为时,就有

当第个位置的信息为时,就有

当第个位置的信息为时,就有

当第个位置的信息为时,就有

最后答案就是

code

/*
* @Author: wxyww
* @Date: 2020-05-07 16:17:44
* @Last Modified time: 2020-05-07 16:46:08
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010,mod = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int f[N][2][2];
char s[N];
int main() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    if(s[1] == '*') f[0][0][1] = 1;
    else if(s[1] == '?') f[0][0][0] = f[0][0][1] = 1;
    else f[0][0][0] = 1;

    for(int i = 1;i <= n;++i) {
        if(s[i] == '0') {
            f[i][0][0] = f[i - 1][0][0];
        }
        if(s[i] == '1') {
            f[i][0][1] = f[i - 1][0][0];
            f[i][0][0] = f[i - 1][1][0];
        }
        if(s[i] == '2') {
            f[i][0][1] = f[i - 1][1][0];
        }
        if(s[i] == '*') {
            f[i][1][0] = f[i][1][1] = (f[i - 1][0][1] + f[i - 1][1][1]) % mod;
        }
        if(s[i] == '?') {
            f[i][1][0] = f[i][1][1] = (f[i - 1][0][1] + f[i - 1][1][1]) % mod;
            f[i][0][0] = f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][0]) % mod;
        }
    }

    cout<<(f[n][0][0] + f[n][1][0]) % mod;
    // cout<<f[1][0][0];
    return 0;
}