# CFR 404 D. Minesweeper 1D ( DP )

Problem - 404D - Codeforces

The first line contains sequence of characters without spaces s1s2... sn (1 ≤ n ≤ 1e6), containing only characters "*", "?" and digits "0", "1" or "2". If character si equals "*", then the i-th cell of the field contains a bomb. If character si equals "?", then Valera hasn't yet decided what to put in the i-th cell. Character si, that is equal to a digit, represents the digit written in the i-th square.

dp[ i ][ j ][ k ] : 已考慮前 i 個字符，倒數第二個字符確定為 j，最後一個字符確定為 k，此時的方案數

O( | S | )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;
const int MOD = ( int ) 1e9 + 7;

string seq;
int dp[ MAXN + 1 ][ 3 + 1 ][ 3 + 1 ]; // 3 for bomb

signed main(){
ios::sync_with_stdio( 0 );
cin >> seq;
for( int i = 0; i < seq.size(); ++i ){
if( seq[ i ] == '*' ){
seq[ i ] = '3';
}
}
dp[ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < seq.size(); ++i ){
for( int j = 0; j <= 3; ++j ){
for( int k = 0; k <= 3; ++k ){
for( int d = ( seq[ i ] == '?' ? 0 : seq[ i ] - '0' ); d <= ( seq[ i ] == '?' ? 3 : seq[ i ] - '0' ); ++d ){
int kc = ( j == 3 ) + ( d == 3 );
if( i != 0 and k < 3 and k != kc ) continue;
if( i != 0 and d == 0 and k == 3 ) continue;
( dp[ i + 1 ][ k ][ d ] += dp[ i ][ j ][ k ] ) %= MOD;
}
}
}
}
int ans = 0;
for( int i = 0; i <= 3; ++i ){
for( int j = 0; j <= 3; ++j ){
if( j < 3 and ( i == 3 ) != j ) continue;
( ans += dp[ seq.size() ][ i ][ j ] ) %= MOD;
}
}
cout << ans << endl;
return 0;
}
```