下文中若无特殊说明，下标默认为 0-index。

思路

考虑两座桥梁什么时候不能同时被维修。

现在要维修若干座桥梁，前提是：任意一座村庄至多只有一条桥梁被维修。

那么，在两座桥梁都连接同一个村庄的时候，这两座桥梁不能同时被维修。

我们可以将第 $i$ 座桥梁看作点，桥梁连接的南北村庄分别为 $x_i$ 和 $y_i$。如果我们选择维修桥 $i$ 和桥 $j$（$i \neq j$），那么有约束：$x_i \neq x_j \land y_i \neq y_j$。

现在，我们需要考虑 $(x_i, y_i)$ 与字符串 $s$ 的关系。

• 第 $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}$。

容易发现，$x_i$ 与子串 $s[0\dots i-1]$ 中 B 的数量有关，$y_i$ 与子串 $s[0\dots i-1]$ 中 A 的数量有关，具体满足：

$$\begin{aligned} x_i &= 1 + (s[0\dots i-1] \ \text{中} \ \mathtt{B} \ \text{的数量}) \\ y_i &= 1 + (s[0\dots i-1] \ \text{中} \ \mathtt{A} \ \text{的数量}) \end{aligned}$$

到这里，你可以把这个问题当作二维的最长单调子序列来做。但是我们不这样做。（等待后人填坑）

再回到之前的限制条件（$x_i \neq x_j \land y_i \neq y_j$），假设 $j < i$，这等价于：

• $(s[0\dots i-1] \ \text{中} \ \mathtt{B} \ \text{的数量}) \neq (s[0\dots j-1] \ \text{中} \ \mathtt{B} \ \text{的数量}) \implies s[j\dots i-1]$ 中必须有 B。
• $(s[0\dots i-1] \ \text{中} \ \mathtt{A} \ \text{的数量}) \neq (s[0\dots j-1] \ \text{中} \ \mathtt{A} \ \text{的数量}) \implies s[j\dots i-1]$ 中必须有 A。

也就是说，如果想要同时维修第 $i$ 座和第 $j$ 座桥梁，子串 $s[j\dots i-1]$ 中必须同时包含 A 和 B。

设 $dp_i$ 为考虑前 $(i+1)$ 座桥，并且维修第 $i$ 座桥时，能够维修桥梁的最大数量（$dp_{i, 0}$）和维修方案数（$dp_{i, 1}$），于是我们可以设计转移方程。

一开始，$dp_i = [1, 1]$，代表只考虑修第 $i$ 座桥。

考虑朴素转移。设桥梁的数量为 $m = 2n - 1$，对于 $i \in [0, m)$，考虑所有的 $j \in [0, i)$，判断子串 $s[j\dots i-1]$ 中是否同时包含 A 和 B，如果成立，说明可以从 $dp_j$ 转移到 $dp_i$。

朴素的转移是 $O(n^3)$ 的，因为判断子串合法性是 $O(n)$ 的。一个显而易见的想法是，对子串中 A 和 B 的数量进行统计（前缀和），或者倒序枚举 $j$，这样可以降到 $O(n^2)$。

:::info[代码实现（$O(n^2)$）]

const int N = (1 << 22) + 5;
const int mod = 1e9 + 7;
int dp[N][2];

array<int, 2> roadwork(string s) {
    memset(dp, 0, sizeof dp);
    int m = s.size() + 1;

    for (int i = 0; i < m; i++) {
        dp[i][0] = dp[i][1] = 1;
        bool hasA = false, hasB = false;
        for (int j = i - 1; j >= 0; j--) {
            if (s[j] == 'A') hasA = true;
            if (s[j] == 'B') hasB = true;
            if (hasA && hasB) { // s[j...i-1] 同时包含 A, B
                if (dp[j][0] + 1 > dp[i][0]) {
                    // 找到了更优的最大数量，直接全盘更新
                    dp[i][0] = dp[j][0] + 1;
                    dp[i][1] = dp[j][1];
                }
                else if (dp[j][0] + 1 == dp[i][0]) {
                    // 找到了同样最大数量的另一种方式，累加方案数
                    dp[i][1] = (dp[i][1] + dp[j][1]) % mod;
                }
            }
        }
    }
    
    int bridges = 0, sum = 0;
    for (int i = 0; i <= m; i++) bridges = max(bridges, dp[i][0]);
    for (int i = 0; i <= m; i++) sum += (dp[i][0] == bridges) * dp[i][1], sum %= mod;
    // 累加具有相同维修桥梁的最大数量的方案数
    return {bridges, sum};
}

:::

但是 $O(n^2)$ 还是太慢了，显然，源头在于枚举待选的合法桥梁 $j$，从中转移的却只有满足 $dp_{j, 0} \geq dp_{i, 0}$ 的 $j$，考虑如何快速找到这个（这些）桥梁 $j$。

考虑维护前缀最优解，设 $mdp_{i}$ 为考虑前 $(i+1)$ 座桥，以其中任意一座桥为结尾时，能够维修桥梁的最大数量（$mdp_{i, 0}$）和维修方案数（$mdp_{i, 1}$），满足：

$$\begin{aligned} mdp_{i, 0} &= \max _{j = 0} ^{i} dp_{j, 0} \\ mdp_{i, 1} &= \sum _{0 \leq j \leq i \land dp_{j, 0} = mdp_{i, 0}} dp_{j, 1} \end{aligned}$$

此外，还需要预处理两个数组 lastA 和 lastB，方便获取到最近的 A 或 B 的下标。

:::info[代码实现（$O(n)$）]

#include <bits/stdc++.h>
using namespace std;

const int N = (1 << 22) + 5;
const int mod = 1e9 + 7;
int dp[N][2];
int lastA[N], lastB[N]; // s[0...i-1] 最后一个 A/B 的下标
int max_dp[N][2];

array<int, 2> roadwork(string s) {
    memset(dp, 0, sizeof dp);
    memset(max_dp, 0, sizeof max_dp);
    memset(lastA, 0, sizeof lastA);
    memset(lastB, 0, sizeof lastB);
    int m = s.size() + 1; // 桥梁数量

    for (int i = 0, cA = -1, cB = -1; i < m; i++) {
        if (s[i] == 'A') cA = i;
        else cB = i;
        lastA[i] = cA, lastB[i] = cB;
    }
    
    for (int i = 0; i < m; i++) {
        dp[i][0] = dp[i][1] = 1;

        // 找到最近的满足 s[j...i-1] 同时包含 A, B 的 j
        int j = -1;
        if (i > 0 && lastA[i - 1] != -1 && lastB[i - 1] != -1) 
            j = min(lastA[i - 1], lastB[i - 1]);
        if (j != -1) {
            dp[i][0] = max_dp[j][0] + 1, dp[i][1] = max_dp[j][1];
            if (max_dp[j][0] == 0) dp[i][1] = 1;
        }
        
        // 更新 map_dp[i]
        int preMax = (i == 0) ? 0 : max_dp[i - 1][0];
        int preWays = (i == 0) ? 0 : max_dp[i - 1][1];
        if (preMax < dp[i][0]) {
            max_dp[i][0] = dp[i][0], max_dp[i][1] = dp[i][1];
        }
        else if (preMax == dp[i][0]) {
            max_dp[i][0] = preMax, max_dp[i][1] = (preWays + dp[i][1]) % mod;
        }
        else {
            max_dp[i][0] = preMax, max_dp[i][1] = preWays;
        }
    }

    return {max_dp[m - 1][0], (max_dp[m - 1][1] + mod) % mod};
}

:::

时间复杂度为 $O(n)$，可以通过此题。