题目大意

略。

题解

由于每一个位置上的描述会涉及当前状态及相邻状态，用 表示**满足前 个字符的要求**，且当前位置状态为 ，后一个位置状态为 时的方案数目。则转移方程不难写出。

初始状态为 ，答案为 。

理论上只刻画当前状态和此前状态似乎也可以，但是讨论就很麻烦。

#include <bits/stdc++.h>
#define INF 2000000000
#define M 1000000007
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, f[1000005][2][2] = {0};
char s[1000005];
void init(){
    scanf("%s", s);
    n = strlen(s);
}
void solve(){
    f[0][0][0] = f[0][0][1] = 1;
    for (int i = 1; i <= n; ++i){
        if (s[i - 1] == '0'){
            f[i][0][0] = f[i - 1][0][0];
        }else if (s[i - 1] == '1'){
            f[i][0][0] = f[i - 1][1][0];
            f[i][0][1] = f[i - 1][0][0];
        }else if (s[i - 1] == '2'){
            f[i][0][1] = f[i - 1][1][0];
        }else if (s[i - 1] == '*'){
            f[i][1][0] = f[i][1][1] = (f[i - 1][0][1] + f[i - 1][1][1]) % M;
        }else {
            f[i][0][0] = f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][0]) % M;
            f[i][1][0] = f[i][1][1] = (f[i - 1][0][1] + f[i - 1][1][1]) % M;
        }
    }
    int ans = (f[n][1][0] + f[n][0][0]);
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}

小结

本题的状态刻画比较精妙。看来寻找一个好的状态表示还是要从题目出发，单靠经验有的时候会使问题复杂化。