（原题解作者：Sujay Konda，使用 GPT-5.4 thinking 翻译）

先分析这个操作在压缩格式下（即由极大连续相同字符段的长度组成的表示）会对二进制串造成什么影响。这个操作等价于：取两个长度相同且相邻的段，将这部分二进制串反转。反转之后，这两段会与外侧的段合并（如果外侧存在段的话）。看下面的例子：

11(0011)00
2,(2,2),2
->
11(1100)00
2+2,2+2

对于边界情况，则有：

(1100)111
(2,2),3
->
(0011)111
2,2+3

实际上，我们可以在首尾补上 $0$，从而把边界情况也统一到普通情况里。于是：

(1100)111
0,(2,2),3,0
->
(0011)111
0+2,2+3,0

这启发我们设计一个区间 DP，其中

$$dp[l][r] = \text{严格位于 } l \text{ 与 } r \text{ 之间的所有段都被删去的方案数}。$$

注意，我们不需要额外存最少操作次数，因为每次操作都会消去两段，所以最少操作次数就是 $(r-l-1)/2$。

状态转移

对于转移，考虑在到达“$l$ 与 $r$ 之间的内容全部被删光”这个状态的前一刻。此时，$l$ 与 $r$ 之间除了 $a$ 和 $b$ 之外，其余都已经被删去了。为了删去 $v_a$ 和 $v_b$，必须满足 $v_a=v_b$。

为了求出 $v_a$ 与 $v_b$ 的值，我们回到普通的二进制串表示，会发现它看起来像这样：

[run of 1s][run of 0s][run of 1s][run of 0s]
   v_l,       v_a,       v_b,        v_r

（或者反过来。）

注意，$l$ 到 $a$ 之间的所有 $0$ 都会并入这个 $0$ 段，$b$ 到 $r$ 之间的所有 $1$ 都会并入这个 $1$ 段，而 $a$ 到 $b$ 之间的 $0$ 和 $1$ 也会分别并入对应的 $0$ 段与 $1$ 段。因此，

$$v_a = [l,b] \text{ 中 } 0 \text{ 的个数},\qquad v_b = [a,r] \text{ 中 } 1 \text{ 的个数}。$$

至于是否属于“反过来”的情况，则取决于 $a$ 所在段对应的字符。

现在定义

$$F(a,b,c)=\frac{(a+b+c)!}{a!b!c!},$$

也就是把长度分别为 $a,b,c$ 的 $3$ 个操作序列交错合并的方案数。那么转移就是

$$dp[l][r] = \sum_{l<a<b<r,\ v_a=v_b} dp[l][a]\cdot dp[a][b]\cdot dp[b][r]\cdot F\!\left(\frac{a-l-1}{2},\frac{b-a-1}{2},\frac{r-b-1}{2}\right)。$$

答案提取

为了提取答案，我们枚举所有满足“$l,r$ 外侧全是补上的 padding”的 $l,r$，也就是说，$l$ 与 $r$ 要么在 padding 中，要么分别是原始最左、最右的段。我们可以额外维护一个布尔型 DP，判断删去 $l,r$ 是否可行；同时保留原本统计方案数的 DP 来计算方案数。

复杂度优化

这样几乎就得到了一个 $O(R^4)$ 的算法，但还差一点：我们还没有说明，为了让算法成立，究竟需要补多少 padding。

对于子任务 3，由于最少操作次数等于 $R/2-1$，所以我们不需要任何 padding，因为我们恰好会删去 $R-2$ 段，最后恰好剩下 $2$ 段。对于其他子任务，你当然可以很容易把 padding 的数量上界估成 $R$，但实际上还能做得更好。假设你进行了一次边界操作：

0,0,a,a,b,...
->
0,a,b+a,....

注意，若想再次进行边界操作，我们至少得先删去这个 $b+a$ 元素，而这至少会把 $a$ 变成 $2a+b$。因此，每当我们需要多补一层 padding，边界处的值至少会翻倍。于是，padding 的数量可以被上界为 $\log N\approx 30$。这样就得到了一个 $O((R+\log N)^4)$ 的算法。

为了进一步优化，注意到 $(a,b)$ 能与 $(l,r)$ 配对，当且仅当

$$\text{$a$ 之前的 $1$ 的个数}+\text{$b$ 之前的 $0$ 的个数} = \text{$r$ 之前的 $1$ 的个数}+\text{$l$ 之前的 $0$ 的个数}。$$

这意味着，当我们增大 $a$ 时，$\text{a 之前的 1\ 的个数}$ 会增大；为了保持平衡，就必须减小 $b$，从而让 $\text{b 之前的 0 的个数}$ 变小。因此，除去 padding 的情况外，每个 $a$ 都只会对应一个 $b$。

注意，在“反过来”的情况里，公式与逻辑完全一样，只需要把 $0$ 和 $1$ 对调即可。这就得到一个 $O((R+\log N)^3+\log^4 N)$ 的算法（其中 padding 的部分贡献了 $\log^4 N$）。

另外，只需要检查长度为偶数的区间，因为每次都会删去 $2$ 段。这样可以显著改善常数，这也是这里 $R=800$ 的原因。

参考代码

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

const int LGN = 30;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using ll = long long;

const int MXM = 1000;

int f[MXM + 1], invf[MXM + 1];

int mulm(int x, int y) {
    return (ll)x * y % MOD;
}

int bpow(int x, int y) {
    return (y == 0 ? 1 : mulm(bpow(mulm(x, x), y / 2), (y % 2 ? x : 1)));
}
int choose(int n, int k) {
    if(k > n) return 0;
    if(k < 0) return 0;
    assert(n >= 0);
    return mulm(mulm(f[n], invf[k]), invf[n - k]);
}

void tc() {
    int M; cin >> M; char c; cin >> c;
    vector<int> a;
    for(int i = 0; i < LGN; i++)
        a.push_back(0);
    for(int i = 0; i < M; i++) {
        int ai; cin >> ai;
        a.push_back(ai);
    }
    for(int i = 0; i < LGN; i++)
        a.push_back(0);
    vector<int> p(M + 2 * LGN);
    for(int i = 2; i < M + 2 * LGN; i++) {
        p[i] = a[i] + p[i - 2];
    }

    vector<vector<bool>> dp(M + 2 * LGN, vector<bool>(M + 2 * LGN));
    vector<vector<int>> dp2(M + 2 * LGN, vector<int>(M + 2 * LGN));

    map<int, vector<pair<int, int>>> trans;

    // add possible transitions from l, r
    auto add_trans = [&] (int l, int r) {
        if(r < LGN || l >= M + LGN) return;
        trans[p[r - 1] + p[l - 1]].push_back({l, r});
    };

    for(int i = 0; i < M + 2 * LGN - 1; i++) {
        dp[i][i + 1] = true;
        dp2[i][i + 1] = 1;
        add_trans(i, i + 1);
    }
    for(int sz = 4; sz <= M + 2 * LGN; sz += 2) {
        for(int l = 1; l + sz - 1 < M + 2 * LGN; l++) {
            int r = l + sz - 1;
            for(auto [u, v] : trans[p[r - 1] + p[l - 1]]) {
               if(l < u && v < r && dp[l][u] && dp[v][r]) {
                    dp[l][r] = true;
                    int ways = mulm(f[(r - l) / 2 - 1], mulm(invf[(r - v) / 2], mulm(invf[(v - u) / 2], invf[(u - l) / 2])));
                    dp2[l][r] += mulm(ways, mulm(dp2[u][v], mulm(dp2[l][u], dp2[v][r])));
                    dp2[l][r] %= MOD;
                }
            }
            if(dp[l][r])
                add_trans(l, r);
        }
    }
    int ans = INF;
    int ans2 = 0;
    for(int l = 0; l <= LGN; l++) {
        for(int r = M + LGN - 1; r < M + 2 * LGN; r++) {
            if(dp[l][r] && (LGN - l) % 2 == (c == '0')) {
                if ((r - l) / 2 < ans) {
                    ans = (r - l) / 2;
                    ans2 = 0;
                }
                if((r - l) / 2 == ans) {
                    ans2 += dp2[l][r];
                    ans2 %= MOD;
                }
            }
        }
    }
    cout << ((ans == INF) ? -1 : ans) << " ";
    cout << ans2 << endl;
}
int main() {

    f[0] = 1;
    for(int i = 1; i <= MXM; i++) {
        f[i] = mulm(f[i - 1], i);
    }
    invf[MXM] = bpow(f[MXM], MOD - 2);
    for(int i = MXM; i >= 1; i--) {
        invf[i - 1] = mulm(invf[i], i);
    }

    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    while(T--) tc();
}

附加问题

Bonus：请在 $O(R^3)$ 时间内解决这个问题。