http://codeforces.com/contest/404/problem/D

Game "Minesweeper 1D" is played on a line of squares, the line's height is 1 square, the line's width is n squares. Some of the squares contain bombs. If a square doesn't contain a bomb, then it contains a number from 0 to 2 — the total number of bombs in adjacent squares.

For example, the correct field to play looks like that: 001*2***101*. The cells that are marked with "*" contain bombs. Note that on the correct field the numbers represent the number of bombs in adjacent cells. For example, field 2* is not correct, because cell with value 2 must have two adjacent cells with bombs.

Valera wants to make a correct field to play "Minesweeper 1D". He has already painted a squared field with width of n cells, put several bombs on the field and wrote numbers into some cells. Now he wonders how many ways to fill the remaining cells with bombs and numbers are there if we should get a correct field in the end.

Input

The first line contains sequence of characters without spaces s1s2... sn (1 ≤ n ≤ 106), 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.

Output

Print a single integer — the number of ways Valera can fill the empty cells and get a correct field.

As the answer can be rather large, print it modulo 1000000007 (109 + 7).

 

题意：长度为n的序列，每个元素是*或者0/1/2或者？，*表示这里埋了一颗炸弹，数字表示这个位置的左右两边位置有0/1/2个炸弹，？表示这里实际是什么不知道。给定一个序列，求合法的方案数。：：:

思路:

①自己想的：

设f(i,0/1/3):只考虑前i个位置，并且第i个位置是0/1/*的方案数(因为不考虑i+1，所以i位置不可能是2)

然后用了很多的if...else...来判断转移，搞得逻辑实际上十分复杂，见代码注释吧。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000000+1000
#define mod 1000000007
#define ll long long

ll n,f[maxn][4];   
char s[maxn];

void dp()
{
	f[0][0]=1;	//只考虑前0个位置，只有"什么都没有"是合理的情况 
	if(s[1]=='?')f[1][0]=f[1][3]=1; //后面要转移到f(i-2)，所有i=1也要初始化 
	else if(s[1]=='*')f[1][3]=1;
	else if(s[1]=='0')f[1][0]=1;
	
	for(int i=2;i<=n;i++)
	{
		if(s[i]=='?')
		{
			f[i][0]=(f[i-1][0]+f[i-1][1])%mod;   //(i是0)i-1,i : 0,0or1,0;  2,0and*,0不合法 
			ll last=0;//(i是*)		//i-2,i-1,i:  0/1,1,* [注意这里i-1是1,在f(i-1)时这里是0，因为不考虑i]
			if(s[i-1]=='1'||s[i-1]=='?')last=f[i-2][0]+f[i-2][1];
					// i-2,i-1,i: *,2,*                 //0/1,1,*	//0/1/*,*,* 
			f[i][3]=((s[i-1]=='2'||s[i-1]=='?'?f[i-2][3]:0)+last+(s[i-1]=='*'||s[i-1]=='?'?f[i-1][3]:0))%mod;
			f[i][1]=f[i-1][3];	//(i是1)i-1,i: *,1,其余不合法 
		}
		else if(s[i]=='*')			//下面与上面是一样的 
		{
			ll last=0;
			if(s[i-1]=='1'||s[i-1]=='?')last=f[i-2][0]+f[i-2][1];
			f[i][3]=((s[i-1]=='2'||s[i-1]=='?'?f[i-2][3]:0)+last+(s[i-1]=='*'||s[i-1]=='?'?f[i-1][3]:0))%mod;
		}
		else if(s[i]=='0')f[i][0]=f[i-1][0]+f[i-1][1];
		else if(s[i]=='1')f[i][1]=f[i-1][3];
	}
}

int main()
{
	//freopen("input.in","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	dp();
	cout<<(f[n][0]+f[n][1]+f[n][2]+f[n][3])%mod<<endl;
	return 0;
}

②官方题解：

设f(i,type):只考虑前i个位置，第i个位置type分别是：

0.填0 

1.填1，*在左

2.填1，*在右

3.填2

4.填*

这样子转移就自然多了，逻辑很清晰(用到了一点未来计算的思想)

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000000+1000
#define mod 1000000007
#define ll long long

ll n,f[maxn][5];   
char s[maxn];

void dp()
{
	f[0][0]=f[0][2]=1;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='?')
		{
			f[i][0]=f[i-1][0]+f[i-1][1],f[i][0]%=mod;
			f[i][1]=f[i-1][4];
			f[i][2]=f[i-1][0]+f[i-1][1],f[i][2]%=mod;
			f[i][3]=f[i-1][4];
			f[i][4]=f[i-1][4]+f[i-1][2]+f[i-1][3],f[i][4]%=mod;
		}
		else if(s[i]=='0')f[i][0]=f[i-1][0]+f[i-1][1],f[i][0]%=mod;
		else if(s[i]=='*')f[i][4]=f[i-1][4]+f[i-1][2]+f[i-1][3],f[i][4]%=mod;
		else if(s[i]=='2')f[i][3]=f[i-1][4];
		else if(s[i]=='1')
		{
			f[i][1]=f[i-1][4];
			f[i][2]=f[i-1][0]+f[i-1][1],f[i][2]%=mod;
		}
	}
}

int main()
{
	//freopen("input.in","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	dp();
	cout<<(f[n][0]+f[n][1]+f[n][4])%mod<<endl;
	return 0;
}