传送门

分析

简单的线性，可以知道当前第位的答案是从位递推出来的，而每一个状态都和其左右两边是否存火有关系，所以可以设计一个三维的DP数组：，表示第位是否存在火，并且第位是否存火，这样就可以把所有的状态表示出来了。
而通过题意可以得到以下的方程：

• 
  
• 
  
  
• 
  
  
• 
  
  
  
  
  所以最后的答案是：

Tags

• DP

参考代码

//#include <bits/stdc++.h>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <list>
#include <set>
#include <sstream>
#include <stack>
#include <string>
//#include <array>
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <map>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
int const MOD = 1e9 + 7;
char s[maxn];
int dp[maxn][2][2];

int main(void) {
    FAST_IO;

    cin >> s + 1;
    int len = strlen(s + 1);
    dp[0][0][0] = dp[0][0][1] = 1;
    for (int i = 1; i <= len; i++) {
        if (s[i] == '0') {
            dp[i][0][0] = (dp[i][0][0] + dp[i - 1][0][0]) % MOD;
        } else if (s[i] == '1') {
            dp[i][0][0] = (dp[i][0][0] + dp[i - 1][1][0]) % MOD;
            dp[i][0][1] = (dp[i][0][1] + dp[i - 1][0][0]) % MOD;
        } else if (s[i] == '2') {
            dp[i][0][1] = (dp[i][0][1] + dp[i - 1][1][1]) % MOD;
        } else if (s[i] == '*') {
            dp[i][1][0] =
                (dp[i][1][0] + dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
            dp[i][1][1] =
                (dp[i][1][1] + dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
        } else {
            dp[i][1][0] += (dp[i - 1][0][1] + dp[i - 1][1][1]);
            dp[i][1][0] %= MOD;
            dp[i][1][1] += (dp[i - 1][0][1] + dp[i - 1][1][1]);
            dp[i][1][1] %= MOD;
            dp[i][0][1] += (dp[i - 1][0][0] + dp[i - 1][1][0]);
            dp[i][0][1] %= MOD;
            dp[i][0][0] += (dp[i - 1][0][0] + dp[i - 1][1][0]);
            dp[i][0][0] %= MOD;
        }
    }
    cout << (dp[len][1][0] + dp[len][0][0]) % MOD <<endl;

    return 0;
}