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; }