代码

#define u32 unsigned
#define fo(i,x,y) for(int i = x;i <= y;++i)
u32 g[540010],*f = g + 270000;
u32 solve(int n, char *s)
{
	u32 cnt = 0,l = 0;
	f[0] = 1;
	int x = 0;
	fo(i,1,n)
	{
		x ^= 1;
		int en = n - i;
		if(i < en) en = i;
		if(s[i - 1] == '(') --f;
		else if(s[i - 1] == ')') ++f;
		else
		{
			int J = x;
			for(int j = x;j + 16 <= en;j += 16)
			{
				f[j] = f[j - 1] + f[j + 1];
				f[j + 2] = f[j + 1] + f[j + 3];
				f[j + 4] = f[j + 3] + f[j + 5];
				f[j + 6] = f[j + 5] + f[j + 7];
				f[j + 8] = f[j + 7] + f[j + 9];
				f[j + 10] = f[j + 9] + f[j + 11];
				f[j + 12] = f[j + 11] + f[j + 13];
				f[j + 14] = f[j + 13] + f[j + 15];
				J = j + 16;
			}
			for(int j = J;j <= en;j += 2) f[j] = f[j - 1] + f[j + 1];
		}
		f[-1] = 0;
	}
	return f[0];
}

评测结果