C++(clang++11) 解法, 执行用时: 37ms, 内存消耗: 29440K, 提交时间: 2021-02-11 14:29:16

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=1e9;
const int N=1e3+100;
const LL P=1000000007;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
void pls(LL &x,LL y){
	x+=y;if(x>=P)x-=P;
}
int n;
int a[N];
LL len[N][N],num[N][N],cnt[N][N],dp[N][N];
int main(){
	int tt=10000;
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	cnt[0][0]=1;
	for(int i=0;i<n;++i){
		if(a[i+1]==-1) --tt;
		for(int j=0;j<=i;++j){
			if(a[i+1]!=1){
				if(j>0) {
					pls(len[i+1][j-1],len[i][j]);
					pls(cnt[i+1][j-1],cnt[i][j]);
					pls(num[i+1][j-1],num[i][j]);
					pls(dp[i+1][j-1],dp[i][j]);
				}
				else{
					pls(len[i+1][j],(cnt[i][j]+len[i][j])%P);
					pls(cnt[i+1][j],cnt[i][j]);
				}
			}
			if(a[i+1]!=0){
				pls(len[i+1][j+1],(cnt[i][j]+len[i][j])%P);
				pls(cnt[i+1][j+1],cnt[i][j]);
				pls(num[i+1][j+1],(num[i][j]+cnt[i][j])%P);
				pls(dp[i+1][j+1],(dp[i][j]+num[i][j]+len[i][j]+cnt[i][j])%P);
			}
		}
	}
	LL ans=0;
	for(int i=0;i<=n;++i) pls(ans,dp[n][i]);
	ans=(ans%P+P)%P;
	for(int i=1;i<=tt;++i) pls(ans,ans);
	printf("%lld\n",ans);
    return 0;
}