【WC2017】挑战-任务3 排行榜

---

时间限制： 3 s
空间限制： 2097152 KB

问题描述

你和同学们找了三道题目用来练习。

这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。

同学们纷纷写出了优秀的代码。现在，他们向你发起了挑战，他们对每个问题都设置了若干个测试数据，这是他们能通过的最大规模的测试数据。现在，他们想看一看你写的代码究竟能超过多少同学的代码，通过多大规模的测试数据。

本题中仅有一个任务，对应一道题和相应的若干个测试点，你需要设计一个能通过尽量多测试点的程序。

任务

我们称一个合法的括号串为：只由左括号和右括号构成，两种括号的数量相等，且任意一个前缀的左括号数量不少于右括号数量的串。 现在给定一个由(、)和?构成的串，问有多少种不同的方案，使得将每个?都替换成一个括号之后，该串变成一个合法的括号串。 两种方案不同，当且仅当至少有一个位置的?被替换成了不同的括号。

我们给出一些括号串的例子：()()()是合法的，(((())()))是合法的，((((是不合法的，())(是不合法的。

对于输入数据(???，答案为2，有(())和()()两种方案。 对于输入数据)???，答案为0，因为不可能有合法的括号串以右括号开头。

接口

unsigned solve(int n, char *s);

其中 n 表示字符串长度，s 为给定的字符串。该函数的返回值是一个整数，表示不同的方案数，模 $2 ^ {32}$。

数据范围

本题共四个测试点：

• 对于第一个测试点，$n = 1000$
• 对于第二个测试点，$n = 120000$
• 对于第三个测试点，$n = 225000$
• 对于第四个测试点，$n = 266666$

提示和说明

本题在32位计算机上运行。

对于所有语言都打开 -O2 编译开关。

---

---