pypy3 解法, 执行用时: 1001ms, 内存消耗: 295264K, 提交时间: 2021-06-03 17:49:56

MOD = int(1e9 + 7)

s = input().strip()
n = len(s)
f = [[[0, 0], [0, 0]] for _ in range(n + 1)]
f[0][0][0] = f[0][0][1] = 1
for i, x in enumerate(s):
	if x == '*':
		f[i + 1][1][0] = (f[i][0][1] + f[i][1][1]) % MOD
		f[i + 1][1][1] = (f[i][0][1] + f[i][1][1]) % MOD
	elif x == '0':
		f[i + 1][0][0] = f[i][0][0]
	elif x == '1':
		f[i + 1][0][0] = f[i][1][0]
		f[i + 1][0][1] = f[i][0][0]
	elif x == '2':
		f[i + 1][0][1] = f[i][1][0]
	elif x == '?':
		f[i + 1][0][0] = (f[i][0][0] + f[i][1][0]) % MOD
		f[i + 1][0][1] = (f[i][0][0] + f[i][1][0]) % MOD
		f[i + 1][1][0] = (f[i][0][1] + f[i][1][1]) % MOD
		f[i + 1][1][1] = (f[i][0][1] + f[i][1][1]) % MOD

print((f[-1][0][0] + f[-1][1][0]) % MOD)

C++ 解法, 执行用时: 34ms, 内存消耗: 32692K, 提交时间: 2021-06-26 12:38:12

#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
const ll mod=1e9+7;
ll f[1000005][2][2];
char s[1000005];
int main(){
	int i;
	scanf("%s",s+1);
	n=strlen(s+1);
	f[0][0][1]=f[0][0][0]=1;
	for(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][1]=f[i][1][0]=(f[i-1][0][1]+f[i-1][1][1])%mod;
		if(s[i]=='?'){
			f[i][0][1]=f[i][0][0]=(f[i-1][1][0]+f[i-1][0][0])%mod;
			f[i][1][0]=f[i][1][1]=(f[i-1][1][1]+f[i-1][0][1])%mod;
		}
	}
	cout<<(f[n][0][0]+f[n][1][0])%mod<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 63ms, 内存消耗: 18096K, 提交时间: 2019-11-23 20:39:42

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<string.h>
const int p=1e9+7;
int n,f[1100000][4],cnt,nj,ans;
char s[1100000];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	f[1][0]=f[1][1]=1;
	fo(i,1,n)
		fo(j,0,3) if (f[i][j]){
			fo(k,0,1){
				cnt=((j&2)>0)+k;
				if ('0'<=s[i]&&s[i]<='2'&&((s[i]!=cnt+'0')||(j&1))) continue;
				if (s[i]=='*'&&(!(j&1))) continue;
				nj=((j&1)<<1)^k;
				f[i+1][nj]+=f[i][j];
				if (f[i+1][nj]>=p) f[i+1][nj]-=p;
			}
		}
	ans=(f[n+1][2]+f[n+1][0])%p;
	printf("%d\n",ans);
	return 0;
}