代码

#include<bits/stdc++.h> 
#pragma GCC optimize("Ofast,inline,unroll-loops,no-stack-protector")
using namespace std;
#define rep(i,a,b) for(signed i(a);i<=b;++i)
#define rep_(i,a,b) for(signed i(a);i^b;++i)
#define req(i,a,b) for(signed i(a);i>=b;--i)
char *s;
int tmp[600001];
unsigned solve(int n,char *s)
{
    int *dp=tmp+270000;
    dp[0]=1;
    req(i,n-1,0)
    {
    	if(s[i]=='(')++dp;
    	else if(s[i]==')')--dp;
    	else
    	{
    		int lim=min(n-i,(int)i);signed j=i&1;
    		for(;j+16<=lim;j+=16) dp[j]=dp[j-1]+dp[j+1],dp[j+2]=dp[j+1]+dp[j+3],dp[j+4]=dp[j+3]+dp[j+5],dp[j+6]=dp[j+5]+dp[j+7],dp[j+8]=dp[j+7]+dp[j+9],dp[j+10]=dp[j+9]+dp[j+11],dp[j+12]=dp[j+11]+dp[j+13],dp[j+14]=dp[j+13]+dp[j+15];
    		for(;j<=lim;j+=2) dp[j]=dp[j-1]+dp[j+1];
    	}
    	dp[-1]=0;
    }
   return dp[0];
}

评测结果