代码

#include<bits/stdc++.h>
using namespace std;
unsigned dp[2][300010];
int hzh[300010];
unsigned solve(int n,char *s)
{
	for(int i=n; i>=1; --i) hzh[i]=hzh[i+1]+(s[i-1]=='('?1:-1);
	dp[0][0]=1;
	signed ax=0;
	for(int i=1; i<=n; ++i)
	{
		ax+=(s[i-1]==')'?-1:1);
		int lim=min(ax,-hzh[i+1]);
		if((i&1)==0)
		{
			dp[i&1][lim/2+1]=dp[i&1][lim/2+2]=0;
			if(s[i-1]=='(')
			{
				dp[i&1][0]=0;
				memcpy(dp[i&1]+1,dp[i-1&1],(lim/2)*4);
			}
			else if(s[i-1]==')')
			{
				memcpy(dp[i&1],dp[i-1&1],(lim/2+1)*4);
			}
			else
			{
				memcpy(dp[i&1],dp[i-1&1],(lim/2+1)*4);
				int j;
				for(j=1; j<=lim/2-7; j+=8)
				{
					dp[i&1][j]+=dp[i-1&1][j-1],
					dp[i&1][j+1]+=dp[i-1&1][j],
					dp[i&1][j+2]+=dp[i-1&1][j+1],
					dp[i&1][j+3]+=dp[i-1&1][j+2],
					dp[i&1][j+4]+=dp[i-1&1][j+3],
					dp[i&1][j+5]+=dp[i-1&1][j+4],
					dp[i&1][j+6]+=dp[i-1&1][j+5],
					dp[i&1][j+7]+=dp[i-1&1][j+6];
				}
				while(j<=lim/2) dp[i&1][j]+=dp[i-1&1][j-1],++j;
			}
		}
		else
		{
			dp[i&1][(lim-1)/2+1]=dp[i&1][(lim-1)/2+2]=0;
			if(s[i-1]=='(')
			{
				memcpy(dp[i&1],dp[i-1&1],((lim-1)/2+1)*4);
			}
			else if(s[i-1]==')')
			{
				memcpy(dp[i&1],dp[i-1&1]+1,((lim-1)/2+1)*4);
			}
			else
			{
				memcpy(dp[i&1],dp[i-1&1],((lim-1)/2+1)*4);
				int j;
				for(j=0; j<=(lim-1)/2-7; j+=8)
				{
					dp[i&1][j]+=dp[i-1&1][j+1],
					dp[i&1][j+1]+=dp[i-1&1][j+2],
					dp[i&1][j+2]+=dp[i-1&1][j+3],
					dp[i&1][j+3]+=dp[i-1&1][j+4],
					dp[i&1][j+4]+=dp[i-1&1][j+5],
					dp[i&1][j+5]+=dp[i-1&1][j+6],
					dp[i&1][j+6]+=dp[i-1&1][j+7],
					dp[i&1][j+7]+=dp[i-1&1][j+8];
				}
				while(j<=(lim-1)/2) dp[i&1][j]+=dp[i-1&1][j+1],++j;
			}
		}
	}
	return dp[n&1][0];
}

评测结果