P11944 [KTSC 2025] 路网维修 / roadwork

版权信息：译自 [2025年度 国际情报 올림피아드 (Olympiad) 代表学生 选拔考试](https://www.ioikorea.or.kr/archives/ioitst/2025/) R1T3。[[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)]

有一条自西向东流的大河，河的南北两岸各有 $n$ 个村庄。北岸的村庄自西向东编号 $A_1\sim A_n$，南岸的村庄自西向东编号 $B_1\sim B_n$。 有 $(2n-1)$ 座桥梁，每座桥梁连接一个南岸村庄和北岸村庄。 具体地说，给定一个长为 $(2n-2)$ 的字符串 $s$，字符集为 $\{\texttt{A},\texttt{B}\}$。 - 第 $0$ 座桥连接 $A_1,B_1$； - $\forall 0\le i\lt 2n-2$，设第 $i$ 座桥连接 $A_x,B_y$： - 若 $s_i=\texttt{A}$，则第 $(i+1)$ 座桥连接 $A_x,B_{y+1}$； - 若 $s_i=\texttt{B}$，则第 $(i+1)$ 座桥连接 $A_{x+1},B_{y}$。 数据保证，$s$ 中恰好有 $(n-1)$ 个 $\texttt{A}$ 和 $(n-1)$ 个 $\texttt{B}$，由此可以导出以下性质： 1. 不存在一条座桥梁，连接了不存在的村庄； 2. 任意两座村庄均通过桥梁连通； 3. 第 $(2n-2)$ 座桥（即最后一座桥）连接 $A_n,B_n$。 现在要维修若干座桥梁，前提是： - 任意一座村庄至多只有一条桥梁被维修。 计算： 1. 在满足以上条件的前提下，至多能维修多少座桥梁。 2. 在满足 1 的前提下，有多少个不同的维修方案。 两个方案不同，当且仅当选择桥梁的集合不同。只需要将第二问的答案对 $(10^9+7)$ 取模。 特别地，如果你只回答第一问，也可以得到部分分，详见【计分方式】。 ### 实现细节 你不需要，也不应该实现 `main` 函数。 你应当实现以下的函数： ```cpp array roadwork(string s); ``` - `s`：长度为 $(2n-2)$ 的字符串 $s$。 - 返回一个数组，第一个元素表示至多能维修多少座桥梁；第二个元素表示方案数对 $(10^9+7)$ 取模后的结果（落在区间 $[0,10^9+7)$ 内）。 - 该函数将被调用 $T$ 次，其中 $T$ 为测试数据组数。

**本题单个测试点内有多组测试数据。** Sample Grader 输入格式如下： 第一行，一个正整数 $T$。 接下来 $T$ 行，每行一个正整数 $n$ 和一个长度为 $(2n-2)$ 的字符串 $s$。

Sample Grader 输出 $T$ 行，每行两个整数，表示对应数据的答案。

### 样例交互 #### 样例交互 $1$ ```cpp roadwork("AB"); ```  显然至多能维修两座桥梁（$(A_1,B_1),(A_2,B_2)$），且这是唯一的方案。所以返回 $[2,1]$。 如果返回 $[2,-1],[2,0]$ 等，将得到 $40\%$ 的分数。 #### 样例交互 $2$ ```cpp roadwork("AABBAABBAABB") ```  至多维修 $6$ 座桥梁，有 $4$ 种方式。所以返回 $[6,4]$。 ### 数据范围 - $1\le T\le 10$； - $2^1\le n\le 2^{21}$； - $s$ 中恰好有 $(n-1)$ 个 $\texttt{A}$ 和 $(n-1)$ 个 $\texttt{B}$。 ### 子任务 子任务 $0$ 为样例。 | 子任务编号 | $n\le$ | 得分 | | :-: | :-: | :-: | | $1$ | $2^{1}$ | $4$ | | $2$ | $2^{3}$ | $5$ | | $3$ | $2^{5}$ | $6$ | | $4$ | $2^{7}$ | $7$ | | $5$ | $2^{9}$ | $8$ | | $6$ | $2^{11}$ | $9$ | | $7$ | $2^{13}$ | $10$ | | $8$ | $2^{15}$ | $11$ | | $9$ | $2^{17}$ | $12$ | | $10$ | $2^{19}$ | $13$ | | $11$ | $2^{21}$ | $15$ | ### 计分方式 如果你正确回答第一问，可以获得 $40\%$ 的分数。 在此前提下，如果你正确回答第二问，可以额外获得 $60\%$ 的分数。