「火」皇家烈焰

直接按题意模拟dp即可..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=2;
const int mod=1e9+7;
char s[N];
ll f[N][M][M];//到了第i个位子,i这个位子有无火,i+1这个位子有无火.
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    f[0][0][1]=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];
            f[i][0][0]%=mod;
        }
        else if(s[i]=='1')
        {
            f[i][0][1]+=f[i-1][0][0];
            f[i][0][1]%=mod;
            f[i][0][0]+=f[i-1][1][0];
            f[i][0][0]%=mod;
        }
        else if(s[i]=='2')
        {
            f[i][0][1]+=f[i-1][1][0];
            f[i][0][1]%=mod;
        }
        else if(s[i]=='*')
        {
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    f[i][1][j]+=f[i-1][k][1],f[i][1][j]%=mod;
        }
        else
        {
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    for(int l=0;l<2;l++)
                        f[i][j][k]+=f[i-1][l][j],f[i][j][k]%=mod;
        }
    }ll ans=f[n][1][0]+f[n][0][0];
    printf("%lld\n",ans);
    return 0;
}