P16332 [DSDOI Round 1] 邓少笔记本

邓少的笔记本上有一个长度为 $n$ 的括号序列 $S$。$S$ 仅由 $\texttt{()*}$ 三种字符组成，其中 $\texttt{*}$ 可以变化成一个 $\texttt{(}$ 或 $\texttt{)}$。 邓少认为一个括号序列是“好的”，当且仅当它满足以下条件： > 对于该序列中 $\texttt{*}$ 的所有可能的变化，都存在一种在这个序列末尾**恰好**添加 $k$ 个**任意括号**的方式，使得整个序列成为合法的括号序列。 例如，当 $k=3$ 时，括号序列 $\texttt{(*(}$ 是“好的”。因为： - 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足上述条件； - 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{()()()}$ 满足上述条件。 而当 $k=3$ 时，括号序列 $\texttt{*((}$ 不是“好的”。因为当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，没有任何一种在末尾恰好添加 $k$ 个任意括号的方式能使该括号序列合法。 需要注意的是，每个 $\texttt{*}$ 可独立变成任意一个括号。也就是说，**每一个 $\texttt{*}$ 的变化情况都不会对其他任何 $\texttt{*}$ 的变化造成影响**。 现在邓少找到了你，希望你告诉他，有多少个不同的 $0 \le x < n$ 满足：将这个括号序列循环左移 $x$ 位后，形成的括号序列是“好的”。

**本题有多组测试数据。** 第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行包含两个正整数 $n,k$，含义如题所示。 第二行包含一个长为 $n$ 的字符串 $S$，表示该括号序列。保证 $S$ 仅由 $\texttt{(}$、$\texttt{)}$ 和 $\texttt{*}$ 三种字符组成。

对于每组测试数据： 输出一行，包含一个整数，表示满足条件的 $x$ 的数量。

### 【样例解释】 对于第一组测试数据： - $x = 0$，此时括号序列为 $\texttt{((*}$。 - 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求； - 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{(()())}$ 满足要求。 - $x = 1$，此时括号序列为 $\texttt{(*(}$。 - 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求； - 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，存在括号序列 $\texttt{()()()}$ 满足要求。 - $x = 2$，此时括号序列为 $\texttt{*((}$。 - 当 $\texttt{*}$ 变化成 $\texttt{(}$ 时，存在括号序列 $\texttt{((()))}$ 满足要求； - 当 $\texttt{*}$ 变化成 $\texttt{)}$ 时，括号序列为 $\texttt{)((}$，无法通过在序列末尾添加 $3$ 个括号使其变为合法括号序列。因此，$x=2$ 不合法。 综上，有两个 $x$ 满足要求，答案为 $2$。 对于第二组测试数据，不存在任何一种方法能满足要求。 对于第三组测试数据，只有 $x = 4,5,6$ 满足要求。 ### 【数据范围】 对于所有测试数据，保证： - $1 \le T \le 10$； - $1 \le n,k \le 10^6$； - $(n+k) \bmod 2 = 0$； - $S$ 仅由 $\texttt{()*}$ 三种字符组成。 | 测试点编号 | $T \le$ | $n,k \le$ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1$ | $1$ | $10$ | $-$ | | $2$ | $5$ | ^ | ^ | | $3 \sim 4$ | $1$ | $10^3$ | ^ | | $5 \sim 6$ | $5$ | ^ | ^ | | $7$ | ^ | $10^5$ | $A$ | | $8$ | ^ | ^ | $B$ | | $9$ | ^ | ^ | $C$ | | $10$ | ^ | ^ | $-$ | | $11 \sim 12$ | $1$ | $10^6$ | ^ | | $13$ | $5$ | ^ | $A$ | | $14$ | ^ | ^ | $B$ | | $15$ | ^ | ^ | $C$ | | $16 \sim 25$ | $10$ | ^ | $-$ | - 特殊性质 $A$：保证 $n = k$。 - 特殊性质 $B$：保证 $S$ 仅由 $\texttt{(}$ 和 $\texttt{)}$ 组成。 - 特殊性质 $C$：保证 $S$ 仅由 $\texttt{(}$ 和 $\texttt{*}$ 组成。